STAT 333 Course Note

STAT 333 Course Note
Table of Contents
1. Fundamental of Probability
2. Random variables and distributions
3. Conditional distribution and conditional expectation
4. Stochastic Processes
5. Poisson Processes
6. Continuous-Time Markov Chain

1. Fundamental of Probability

1.1. What's Probability

1.1.1. Examples

Coin toss
- "H" - head
- "T" - tail
Roll a dice
- every number in the set: $\{1,2,3,4,5,6\}$
Tomorrow weather
- {sunny, rainy, cloudy,...}
Randomly pick a number in $[0, 1]$

Although things are random, they are not haphazard/arbitrary. There are "patterns"

Example 1

If we repeat tossing a coin, then the fraction of times that we get a "H" goes to $\frac{1}{2}$ as the number of toss goes to infinity.

$\frac{\#\; of \;"H"}{total\; \#\; of\; toss} = \frac{1}{2}$

This number $1/2$ reflects how "likely" a "H" will appear in one toss (if the experiment is not repeated)

1.2. Probability Models

The Sample space $\Omega$ is the set consisting of al the possible outcomes of a random experiment.

1.2.1. Examples

$\{H, T\}$
$\{1,2,3,4,5,6\}$
$\{sunny, rainy, cloudy, ...\}$
$[0, 1]$

An event $E\in \Omega$ is a subset of $\Omega$

for which we can talk about "likelihood of happening"; for example

in 2:
- {getting an even number} = {2, 4, 6}
in 4:
- $\{the \;point\; is\; between\; 0\; and\; 1/3\} = [0, \frac{1}{3}]$ is an event
- $\{the\; point\; is\; rational\} = Q \cap [0, 1]$

We say an event $E$ "happens", if the result of the experiment turns out to belong to $E$ (a subset of $\Omega$ )

A probability $P$ is a set function ( a mapping from events to real numbers)

$\begin{aligned} P: & \xi \rightarrow R \\ & E \rightarrow P(E) \end{aligned}$

which satisfies the following 3 properties:

$\forall E \in \xi, 0 \leq P(E) \leq 1$
$P(\Omega) = 1$
For
- countably many disjoint events $E_1, E_2,...,$ we have $P(U_{i=1}^{\infty}E_i) = \sum_{i=1}^{\infty}P(E_i)$
- countable: $\exists$ 1-1 mapping to natural numbers $1,2,3,...$

Intuitively, one can think the probability of an event as the "likelihood/chance" for the event happens. If we repeat the experiment for a large number of events, the probability is the fraction of time that the event happens

$P(E) = \lim_{n\rightarrow\infty} \frac{\text{\# of times the E happens in n trials}}{n}$

1.2.1.1. Example 2

$\begin{aligned} &P(\{1\})=P(\{2\})=\ldots=P(\{6\})=\frac{1}{6} \\ &E = \{\text{even number}\} = \{2,4,6\} \\ \Rightarrow \;\; &P(E) = P(\{2\}\cup P(\{4\})) \cup P(\{6\}) = \frac{1}{2} \end{aligned}$

Properties of probability:

$P(E) + P(E^c) = 1$
$P(\emptyset)=0$
$E_1\subseteq E_2 \Rightarrow P(E_1)\leq P(E_2)$
$P(E_1 \cup E_2) = P(E_1) + P(E_2) - P(E_1 \cap E_2)$ - $P(E_1 \cap E_2)$ : $E_1$ and $E_2$ happen

1.2.2. Remark: why do we need the notion of event?

If the sample space $\Omega$ is discrete, then everything can has at most countable elements be built from the "atoms"

$\begin{aligned} \Omega = \{w_1, w_2, \ldots\} \\ P(w_1) = P_i \\ P_i \in [0, 1], \sum_{i=1}^\infty P_i = 1 \end{aligned}$

Then for any event $E=\{w_1, i \in I\}$ , $P(E) = \sum_{i \in I}P_i$

However, if the sample space $\Omega$ is continuous; e.g, $[0,1]$ in Example 4, then such a construction can not be done for any $x\in [0, 1]$ we get $P(\{x\} = 0$ ( $x$ : the point is exactly $x$ )

We can not get $P([0, \frac{1}{3}])$ by adding $P(\{x\})$ for $x\leq \frac{1}{3}$ .

This is why we need the notion of event; and we define $P$ as a set function from $\xi$ to $R$ rather than a function from $\Omega$ to $R$

To summarize: A Probability Space consists of a triplet $(\Omega, \xi, P)$ :

$\Omega$ : sample space,
$\xi$ : collection of events
$P$ : probability

1.3. Conditional Probability

If we know some information, the probability of an event can be updated

Let $E$ , $F$ be two events $P(F) > 0$

The conditional probability of $E$ , given $F$ is

$P(E\mid F) = \frac{P(E \cap F)}{P(F)}$

Again, think probability as the long-run frequency:

$\begin{aligned} P(E \cap F) &= \lim_{n\rightarrow\infty}\frac{\# of\; times\; E\; and\; F\; happen\; in\; n\; trails}{n} \\ P(F) &= \lim_{n\rightarrow\infty}\frac{\# of\; times\; F\; happen\; in\; n\; trails}{n} \\ \Rightarrow \frac{P(E\cap F)}{P(F)} &= \lim_{n\rightarrow\infty}\frac{\# of\; times\; E\; and\; F\; happen}{\# of \;times \;F \;happens} \end{aligned}$

By definition

$P(E\cap F) = P(E\mid F) \cdot P(F)$

1.4. Independence

Def: Two events $E$ and $F$ are said to be independent, if $P(E\cap F)=P(E)\cdot P(F)$ ; denoted as $E\perp\!\!\!\perp F$ . This is different rom disjoint.

Assume $P(F)>0$ , then $E\perp\!\!\!\perp F \Leftrightarrow P(E|F)=P(E)$ ; intuitively, knowing $F$ does not change the probability of $E$ .

Proof:

$\begin{aligned} E\perp\!\!\!\perp F & \Leftrightarrow P(E\cap F) = P(E)\cdot P(F) \\ & \Leftrightarrow \frac{P(E\cap F)}{P(F)} = P(E) \\ & \Leftrightarrow P(E|F) = P(E) \end{aligned}$

More generally, a sequence of events $E_1, E_2, \ldots$ are called independent if for any finite index set $I$ ,

$P(\bigcap_{i\in I}E_i)=\prod_{i\in I} P(E_i)$

1.5. Bayes' rule and law of total probability

Theorem: Let $F_1, F_2,\ldots$ be disjoint events, and $\bigcap_{i=1}^\infty F_i=\Omega$ , we say $\{F_i\}_{i=1}^\infty$ forms a "partition" of the sample space $\Omega$

Then $P(E)=\sum_{i=1}^\infty P(E|F_i)\cdot P(F_i)$

Proof: Exercise

Intuition: Decompose the total probability into different cases.

$P(E\cap F_2) = P(E|F_2)\cdot P(F_2)$

1.5.1. Bayes' rule

$P(F_i | E) = \frac{P(E|F_i)\cdot P(F_i)}{\sum_{j=1}^\infty P(E|F_j)\cdot P(F_j)}$

Bayes' rule tells us how to find conditional probability by switching the role of the event and the condition.

Proof:

$\begin{aligned} P(F_i | E) & = \frac{P(F_i\cap E)}{P(E)} & \hspace{1em}\text{definition of condition probability} \\ & = \frac{P(E|F_i)P(F_i)}{P(E)} \\ & = \frac{P(E|F_i)P(F_i)}{\sum_{j=1}^\infty P(E|F_j)P(F_j)} & \text{law of total probability} \end{aligned}$

2. Random variables and distributions

2.1. Random variables

$(\Omega,\xi, P)$ : Probability space.

Definition: A random variable $X$ (or r.v.) is a mapping from $\Omega$ to $\R$

$\begin{aligned} X : & \Omega\rightarrow \R \\ & \omega \rightarrow X(\omega) \end{aligned}$

A random variable transforms arbitrary "outcomes" into numbers.

$X$ introduces a probability on $R$ . For $A\subseteq R$ , define

$\begin{aligned} P(X\in A) :&= P(\{X(\omega)\in A\}) \\ &= P(\{\omega:X(\omega)\in A\}) \\ &= P(X^{-1}(A)) \end{aligned}$

From now on, we can often "forget" te original probability space and focus on the random variables and their distributions.

Definition: let $X$ be a random variable. The CDF(cumulative distribution function) $F$ of $X$ is defined by

$F(x) = P(X\leq x) = P(X\in(-\infty, x])) \\ X: \text{random variable}, x: \text{number}$

Properties of cdf:

$F$ is non-decreasing. $F(x_1)\leq F(x_2), x_1 < x_2$
limits
- $\lim_{x\rightarrow -\infty}F(x) = 0$
- $\lim_{x\rightarrow\infty}F(x)=1$
$F(x)$ $F (x)$ is right continuous
- $lim_{x\downarrow a}F(x) = F(a)$ : $x$ decreases to $a$ (approaching from the right)
- Hint: $\{x\leq a\}=\bigcap_{i=1}^\infty\{X\leq a_i\}$ for $a_i\downarrow a$

2.2. Discrete random variables and distributions

A random variable $X$ is called discrete if it only takes values in an at most countable set $\{x_1, x_2, \ldots\}$ (finite or countable).

The distribution of a discrete random variable is fully characterized by its probability mass function(p.m.f)

$p(x):=P(X=x); x=x_1, x_2, \ldots$

Properties of pmf:

$p(x)\geq 0, \;\;\forall x$
$\sum_ip(x_i) = 1$

Q: what does the cdf of a discrete random variable look like?

2.2.1. Examples of discrete distributions

1. Bemoulli distribution

$\begin{aligned} p(1) &= P(X=1)=p \\ p(c) &= P(X=c) = 1-p \\ p(x) &= 0 \quad otherwise \end{aligned}$

Denote $X\sim Ber(p)$

2.Binomial distribution

$\begin{aligned} p(k) = P(X=k) = \lgroup\stackrel{n}{k}\rgroup p^k(1-p)^{n-k} \end{aligned}$

$X\sim Bin(n, p)$ to choose $k$ successes.
Binomial distribution is the distribution of number of successes in $n$ independent trials; each having probability $p$ of success.

3.Geometric distribution

$p(k) = P(X=k)=(1-p)^{k-1}p \\$

$(1-p)^{k-1}: \text{the first k-1 trials are all failures},\;\; p: \text{success in }k^{th}\text{ trial}$

$X\sim Geo(p)$
$X$ is the number of trials needed to get the first success in $n$ independent trials with probability $p$ of success each
$X$ has the memoryless property $P(X>n+m|X>m) = P(x>n) \hspace{2em} n, m=0,1,\ldots$

Memoryless property:

$p(X>n+m|X>m)=P(X>n)$

Proof:

$\begin{aligned} P(X>k) & = \sum_{j=k+1}^\infty P(X=j) \\ & = \sum_{j=k+1}^\infty (1-p)^{j-1}p \\ & = (1-p)^kp \cdot \frac{1}{1-(1-p)} \\ & = (1-p)^k \\ \end{aligned}$

$\begin{aligned} P(X>n+m|x>m) &= \frac{P(X>n+m\bigcap X>m)}{P(X>m)} \\ &= \frac{P(X>n+m)}{P(X>m)} = \frac{(1-p)^{n+m}}{(1-p)^m} = (1-p)^n=P(X>n) \end{aligned}$

Intuition: The failures in the past have no influence on how long we still need to wait to get the first success in the future

4. Poisson distribution

$p(k)=P(X=k)=\frac{\lambda^k e^{-\lambda}}{k!}, k=0,1,2,\ldots, \lambda > 0$

Other discrete distributions:

negative binomial
discrete uniform

2.3. Continuous random variables and distributions

Definition: A random variable $X$ is called continuous if there exists a non-negative function $f$ , such that for any interval $[a,b]$ , $(a,b)$ or $[a,b)$ :

$P(X\in[a,b]) = \int_a^b f(x)dx$

The function $f$ is called the probability density function(pdf) of $X$

Remark: probability density function(pdf) is not probability. $P(X=x)=0$ if $X$ is continuous. The probability density function $f$ only gives probability when it is integrated.

If $X$ is continuous, then we can get cdf by:

$F(a)=P(X\in(-\infty, a])=\int^a_{-\infty} f(x)dx$

hence, $F(x)$ is continuous, and differentiable "almost everywhere".

We can take $f(x)=F'(x)$ when the derivative exists, and $f(x)=$ arbitrary number otherwise often to choose a value to make $f$ have some continuity.

Property of pdf:

$f(x)\leq 0$ , $x\in R$
$\int_{-\infty}^\infty f(x)dx = 1$
For $A\subseteq R, P(X\in A)=\int_A f(x)dx$

2.3.1. Example of continuous distribution

Exponential distribution

$f(x)= \begin{cases} \begin{aligned} &\lambda e^{-\lambda x} &, x\geq 0 \\ &0 &, x\leq 0 \end{aligned} \end{cases} \\ X\sim Exp(x)$

Other continuous distributions:

Normal distribution
Uniform distribution

Exercises:

Find the cdf of $X\sim Exp(x)$
$\begin{aligned} F(k) = P(X\leq k) &= \int_{-\infty}^k f(x)dx \\ &= \int_0^k \lambda e^{-\lambda x}dx \\ &= -e^{-\lambda x} \Big|^k_0 \\ &= -e^{-\lambda k} - (-e^0) \\ &= 1 - e^{-\lambda k} \end{aligned}$
Show that the exponential distribution has the memoryless property:
$P(X>t+s|X>t)=P(X>s)$

2.4. Joint distribution of r.v's

Let $X$ and $Y$ be two r.v's. defined on the same probability space $(\Omega, \xi, P)$

For each $\omega \in \Omega$ , we have at the same time $X(\omega)$ and $Y(\omega)$ . Then we can talk about the joint behavior of $X$ and $Y$

Two joint distribution of r.v's is characterized by joint cdf, joint pmf(discrete case) or joint pdf(continuous case).

Joint cdf:
- $F(x,y) = P(X<x, Y<y)$
Joint pmf:
- $f(x,y)=P(X=x, Y=y)$
joint pdf $f(x,y)$ $f (x, y)$ such that for $a<b, c<d$ $a < b, c < d$
- $P(X,Y)\in(a,b]\times(c,d] = P(X\in(a,b], Y\in(c,d])=\int_a^b\int_c^d f(x,y)dy dx$
- Equivalently:
  1. $F(x,y)=\int_{-\infty}^x\int_{-\infty}^y f(s,t)dtds \\\text{and} \\$ $f(x,y)=\frac{\partial^2}{\partial x \partial y}F(x,y)$
  2. $P((X,Y)\in A) = \int\int_A f(x,y)dxdy$ for $A\subseteq R^2$

Definition: Two r.v's $X$ and $Y$ are called independent, if for all sets $A,B\subseteq R$ ,

$P(X<A,Y<B)=P(X\in A)\cdot P(Y\in B)$

( $\{X\in A\}$ and $\{Y\in B\}$ are independent events)

Theorem: Two r.v's $X$ and $Y$ are

independent, if and only if
$F(x,y)=F_x(x)F_y(y); x,y\in R$ ; where $F_x$ : cdf of x; $F_y$ : cdf of y
$f(x,y)=f_x(x)f_y(y); x,y\in R$ ; where $f$ is the joint pmf/pdf of $X$ and $Y$ ; $f_x$ , $f_y$ are marginal pmf/pdf of $X$ and $Y$ , respectively

Proof:

1. $\Rightarrow$ 2.

If $X \perp\!\!\!\perp Y$ , then by definition,

$F(x,y)=P(X\in(-\infty, x],Y\in(-\infty, y])) = P(X\in(-\infty, x]))\cdot P(Y\in(-\infty,y])) = F_x(x)F_y(y)$

2. $\Rightarrow$ 3.

Assume $F(x,y)=F_x(x)\cdot F_y(y)$ ,

$\begin{aligned} f(x,y)=\frac{\partial^2}{\partial x \partial y}F(x,y) & = \frac{\partial^2}{\partial x \partial y} F_x(x)F_y(y) \\ &= (\frac{\partial}{\partial x}F_x(x))(\frac{\partial}{\partial y}F_y(y)) \\ &= f_x(x)f_y(y) \end{aligned}$

3. $\Rightarrow$ 1.

Assume $f(x,y)=f_x(x)f_y(y)$ ; For $A,B\subseteq R$ ,

$\begin{aligned} P(X\in A, Y\in B) &= \int_{y\in B}\int_{x\in A} f(x,y) dxdy \\ &= \int_{y\in B}\int_{x\in A} f_x(x)f_y(y)dxdy \\ &= (\int_{x\in A} f_x(x)dx) (\int_{y\in B} f_y(y)dy) \\ &= P(X\in A)P(Y\in B) \end{aligned}$

2.5. Expectation

Definition: For a r.v $X$ , the expectation of $g(x)$ is defined as

$\mathbb{E}(g(X))= \begin{cases} \begin{aligned} & \sum_{i=1}^\infty g(x_i)P(X=x_i) & \text{for discrete } X \\ & \int_{-\infty}^\infty g(x)f(x)dx & \text{for continuous} X \end{aligned} \end{cases}$

Let $X$ , $Y$ be two r.v's; then the expectation of $g(X,Y)$ is defined in a similar way.

$\mathbb{E}(g(X,Y)) = \begin{cases} \begin{aligned} &\sum_i\sum_j g(x_i,y_j)P(X=x_i, Y=y_j)\\ & \int\int g(x_i, y_j)f(x,y)dxdy \end{aligned} \end{cases}$

2.5.1. Properties of expectation

Linearity:expectation of $X$ $X$ : $\mathbb{E}(X)= \begin{cases} \sum x_i P(X=x_i) \\ \int_{-\infty}^{\infty} xf(x)dx \end{cases}$ $E (X) = {\sum x_{i} P (X = x_{i}) \int_{- \infty}^{\infty} x f (x) d x$ , $g(X)=x$ $g (X) = x$
- $\mathbb{E}(ax+b)=a\mathbb{E}(x)+b$
- $\mathbb{E}(X+Y)=\mathbb{E}(X)+\mathbb{E}(Y)$
If $X\perp \!\!\! \perp Y$ $X ⊥ ⊥ Y$ , then $\mathbb{E}(g(X)h(Y))=\mathbb{E}(g(X))\cdot \mathbb{E}(h(Y))$ $E (g (X) h (Y)) = E (g (X)) \cdot E (h (Y))$
- proof: (continuous case)
- $\begin{aligned} \mathbb{E}(g(X)h(Y)) &= \int_{-\infty}^\infty\int_{-\infty}^\infty g(x)h(y)f(x,y)dxdy \\ &= \int_{-\infty}^\infty\int_{-\infty}^\infty g(x)h(y)f_X(x)f_Y(y)dxdy \\ &= \int_{-\infty}^\infty g(x)f_X(x)\cdot\int_{-\infty}^\infty h(y)f_Y(y)dy\\ \end{aligned}$
- In particular, $\mathbb{E}(XY)=\mathbb{E}(X)\mathbb{E}(Y)$ if $X\perp \!\!\! \perp Y$

2.5.2. Definitions

Definition: The expectation $\mathbb{E}(X^n)$ is called the n-th moment of $X$ :

1st moment: $\mathbb{E}(X)$
2st moment: $\mathbb{E}(X^2)$

Definition: The variance of a r.v $X$ is defined as:

$Var(x)=\mathbb{E}((X-\mathbb{E}(X))^2) \text{ also denoted as } \sigma^2, \sigma_x^2$

Definition: the covariance of the r.v's $X$ and $Y$ is defined as:

$Cov(X,Y)=\mathbb{E}[(X-\mathbb{E}(X))(Y-\mathbb{E}(Y))]$

Thus $Var(X)=Cov(X,X)$

Definition: the correlation between $X$ and $Y$ is defined as:

$Cor(X,Y)=\frac{Cov(X,Y)}{\sqrt{Var(X)Var(Y)}}$

Fact: $Var(X)=\mathbb{E}(X^2)-(\mathbb{E}(X))^2$

Proof:

$\begin{aligned} Var(X) &= \mathbb{E}((X-\mathbb{E}(X))^2) \\ &= \mathbb{E}(X^2-2X\mathbb{E}(X)+(\mathbb{E}(X))^2) \\ &= \mathbb{E}(X^2)-2\mathbb{E}(X\mathbb{E}(X))+(\mathbb{E}(X))^2 \\ &= \mathbb{E}(X^2)-2(\mathbb{E}(X))^2+(\mathbb{E}(X))^2 \\ &= \mathbb{E}(X^2)-(\mathbb{E}(X))^2 \quad\quad\blacksquare \end{aligned}$

Fact: $Cov(X,Y)=\mathbb{E}(XY)-\mathbb{E}(X)\mathbb{E}(Y)$

Proof:

$\begin{aligned} Cov(X,Y) &=\mathbb{E}[(X-\mathbb{E}[X])(Y-\mathbb{E}[Y])] \\ &=\mathbb{E}[XY - X\mathbb{E}[Y]-Y\mathbb{E}[X] + \mathbb{E}[X]\mathbb{E}[Y]] \\ &=\mathbb{E}[XY] - \mathbb{E}[X\mathbb{E}[Y]] - \mathbb{E}[Y\mathbb{E}[X]] + \mathbb{E}[E]X]\mathbb{E}[Y]) \\ &=\mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y] - \mathbb{E}[Y]\mathbb{E}[X] + \mathbb{E}[X]\mathbb{E}[Y] \\ &=\mathbb{E}[XY]-\mathbb{E}[X]\mathbb{E}[Y] \quad\quad\blacksquare \end{aligned}$

Variance and covariance are translation invariant. Variance is quadratic, covariance is bilinear.

$Var(aX+b)=a^2\cdot Var(X)$

$Cov(aX+b, cY+d)=ac\cdot Cov(X,Y)$

Proof: $Var(aX+b)=a^2\cdot Var(X)$

$\begin{aligned} Var(aX+b) &= \mathbb{E}((aX+b)^2)-(\mathbb{E}(aX+b))^2 \\ &= \mathbb{E}(a^2X^2 + 2abX + b^2) - (a\mathbb{E}(X)+b)^2 \\ &= a^2\mathbb{E}(X^2) + 2ab\mathbb{E}(X)+b^2 - a^2\mathbb{E}^2(X) - ab\mathbb{E}(X) - b^2 \\ &= a^2\mathbb{E}(X^2)-a^2\mathbb{E}^2(X) \\ &= a^2 Var(X) \quad\quad\blacksquare \end{aligned}$

Proof: $Var(X+Y) = Var(X)+Var(Y)+2Cov(X,Y)$

$\begin{aligned} Var(X+Y) &= \mathbb{E}[(X+Y)^2] - E^2[X+Y] \\ &=\mathbb{E}[X^2 + XY + Y^2] - (\mathbb{E}[X]+\mathbb{E}[Y])^2 \\ &=\mathbb{E}[X^2] + \mathbb{E}[XY] + \mathbb{E}[Y^2] - E^2[X] - 2\mathbb{E}[X]\mathbb{E}[Y] - E^2[Y] \\ &=(\mathbb{E}[X^2]-E^2[X]) + (\mathbb{E}[Y^2]-E^2[Y]) + (\mathbb{E}[XY]-2\mathbb{E}[X]\mathbb{E}[Y]) \\ &=Var(X) + Var(Y) + 2 Cov(X,Y) \quad\quad\blacksquare \end{aligned}$

If $X\perp \!\!\! \perp Y$ , then $Cov(X,Y)=0$ and $Var(X+Y)=Var(X)+Var(Y)$

Proof:

$\begin{aligned} & Cov(X,Y)=\mathbb{E}(XY)-\mathbb{E}(X)\mathbb{E}(Y) \\ & \text{we know:} \\ & X\ \perp\!\!\!\perp Y\Rightarrow \mathbb{E}(XY)=\mathbb{E}(X)\mathbb{E}(Y) \\ & \text{Thus, } Cov(X,Y)=0 \Rightarrow Var(X+Y)=Var(X)+Var(Y)+2Cov(X,Y) \\ & \text{So we see independence} \Rightarrow \text{Covariance is 0: "uncorrelated"} \\ & \text{the converse is not true.} \\ & Cov(X,Y)=0 \cancel{\rightarrow} \text{independence} \end{aligned}$

Remarks

We have $\mathbb{E}(X+Y)=\mathbb{E}(X)+\mathbb{E}(Y)$ .

If $X\perp \!\!\! \perp Y$ , we also have:

$\mathbb{E}(XY) = \mathbb{E}(X)\mathbb{E}(Y)$ , and
$Var(X+Y)=Var(X)+Var(Y)$

It's important to remember that the first result and the other two results are of very different nature. While $\mathbb{E}(X+Y)=\mathbb{E}(X)+\mathbb{E}(Y)$ is a property of expectation and holds unconditionally;

the other two, $\mathbb{E}(XY) = \mathbb{E}(X)\mathbb{E}(Y)$ and $Var(X+Y)=Var(X)+Var(Y)$ , only hold if $X\perp \!\!\! \perp Y$ .

It is more appropriate to consider them as properties of independence rather than properties of expectation and variance

2.6. Indicator

A random variable $I$ is called an indicator, if

$I(w)= \begin{cases} \begin{aligned} & 1 & \omega\in A \\ & 0 & \omega\cancel{\in} A \end{aligned} \end{cases}$

$E(I_A) = P(A)$

for some event $A$

For $A$ given, $I$ is also elevated as $I_A$

The most important property of indicator is its expectation gives the probability of the event $\mathbb{E}(I_A)=\mathbb{P}(A)$

Proof:

$\begin{aligned} \mathbb{P}(I_A=1) &= \mathbb{P}({\omega:I_A(\omega=1)}) \\ &= \mathbb{P}({\omega:\omega\in A}) \\ &= \mathbb{P}(A) \end{aligned}$

$\mathbb{P}(I_A=0) = 1- \mathbb{P}(A) \Rightarrow \mathbb{E}(I_A)=1\cdot \mathbb{P}(A)+c\cdot (1-\mathbb{P}(A)) = \mathbb{P}(A)$

2.6.1. Example

we see $I_A\sim Ber(\mathbb{P}(A))$

Let $X\sim Bin(n,p)$ , $X$ is number of successes in $n$ Bernoulli trials, each with probability $p$ of success

$\Rightarrow X=I_1+\cdots+I_n$

where $I_1,\cdots,I_n$ are indicators for independent events. $I_i=1$ if th $i$ the trial is a success. $I_i=0$ if the $i$ th trial is a failure.

Hence $I_i$ are idd(independent and identically distributed) r.v's

$\begin{aligned} \Rightarrow \mathbb{E}(X) &= \mathbb{E}(I_1+\cdots+I_N) \\ &= \mathbb{E}(I_1)+\cdots+\mathbb{E}(I_n) \\ &= p + \cdots + p = n\cdot p \end{aligned}$

$\begin{aligned} Var(X) &= Var(I_1+\cdots+I_n) \\ &= Var(I_1)+\cdots+Var(I_n) \\ &= n\cdot Var(I_i) \\ &= n\cdot p(1-p) \end{aligned}$

$Var(I_1)=\mathbb{E}(I_1^2)-(\mathbb{E}(I_1))^2 = \mathbb{E}(I_1)-(\mathbb{E}(I_1))^2=p-p^2=p(1-p)$

2.6.1. Example 3

Let $X$ be a r.v. taking values in non-negative integers, then

$\mathbb{E}(X) = \sum_{n=0}^\infty P(X>n)$

Proof:

Note that $X=\sum_{n=0}^\infty I_n$ where $I_n = I_{x>n}$ . ( $x>n$ is an event)

$\begin{aligned} \mathbb{E}(X) &= \mathbb{E}(\sum_{n=0}^\infty I_n) \\ &= \sum_{n=0}^\infty \mathbb{E}(I_n) \\ &= \sum_{n=0}^\infty P(X>n) \end{aligned}$

In particular, let $X\sim Geo(p)$ . As we have seen, $P(X>n)=(1-p)^n\Rightarrow$

$\begin{aligned} \mathbb{E}(X) &= \sum_{n=0}^\infty P(X>n) \\ &= \sum_{n=0}^\infty (1-p)^n \\ &= \frac{1}{1-(1-p)} = \frac{1}{p} \end{aligned}$

2.7. Moment generating function

Definition: Let $X$ be a r.v. Then the function $M(t)=\mathbb{E}(e^{tX})$ is called the moment generating function(mgf) of $X$ , if the expectation exists for all $t\in (-h, h)$ for some $h>0$ .

Remark: The mgf is not always well-defined. It is important to check the existence of the expectation.

2.7.1. Properties of mgf

Moment Generating Function generates moments
- Theorem:
  - $M(0) = 1$
  - $M^{(k)}(0) = \mathbb{E}(X^k), k=1,2,\ldots$ $M^{(k)} (0) = E (X^{k}), k = 1, 2, \dots$ ( $M^{(k)}=\frac{d^k}{dt^k} M(t)|_{t=0}$ $M^{(k)} = \frac{d ^{k}}{d t ^{k}} M (t) ∣_{t = 0}$ )
    - Proof:
      $\begin{aligned} & M(0) = \mathbb{E}(e^{0\cdot X})=\mathbb{E}(1) = 1 \\ M^{(k)}(0) &= \frac{d^k}{dt^k} \mathbb{E}(e^{t\cdot X)})|_{t=0} \\ &= \mathbb{E}(\frac{d^k}{dt^k} e^{tX}|_{t=0}) \\ &= \mathbb{E}(X^k) \end{aligned}$
  - As a result, we have: $M(t)=\sum_{k=0}^\infty \frac{M^{(k)}(0)}{k!} t^k = \sum_{k=0}^\infty \frac{E*X^k}{k!}t^k$ (a method to get moment of a r.v)
$X\perp \!\!\! \perp Y$ $X ⊥ ⊥ Y$ , with mgf's $M_x, M_y$ $M_{x}, M_{y}$ . Let $M_{X+Y}$ $M_{X + Y}$ be the mgf of $X+Y$ $X + Y$ . then
$M_{X+Y}(t)=M_X(t)M_Y(t)$
- Proof:
$\begin{aligned} M_{X+Y}(t) &= \mathbb{E}(e^{t(X+Y)}) \\ &= \mathbb{E}(e^{tx}e^{ty}) \\ &= \mathbb{E}(e^{tx})\mathbb{E}(e^{ty}) \\ &= M_X(t)M_Y(t) \end{aligned}$
The mgf completely determines the distribution of a r.v.
- $M_X(t)=M_Y(t)$ for all $t\in (-h,h)$ for some $h>0$ , then $X\stackrel{d}{=}Y$ . ( $\stackrel{d}{=}$ : have the same distribution)
- Example: Let $X\sim Poi(\lambda_1)$ $X \sim P o i (λ_{1})$ , $Y\sim Poi(\lambda_2)$ $Y \sim P o i (λ_{2})$ . $X\perp \!\!\! \perp Y$ $X ⊥ ⊥ Y$ . Find the distribution of $X+Y$ $X + Y$
  - First, derive the mgf of a Poisson distribution.
    
    $\begin{aligned} M_X(t) &= \mathbb{E}(e^{tX}) \\ &= \sum_{n=0}^\infty e^{tn}\cdot P(X=n) \\ &= \sum_{n=0}^\infty e^{tn}\cdot \frac{\lambda_1^n}{n!}e^{-\lambda_1} \\ &= \sum_{n=0}^\infty \frac{(e^t\cdot\lambda_1)^n}{n!}\cdot e^{-\lambda_1} \\ \text{we know that } \sum_{n=0}^\infty \frac{(e^t\lambda_1)^n}{n!}=e^{e^t\cdot\lambda_1}.& \text{(Since } \frac{(e^t\lambda_1^n)}{n!}e^{-e^t\lambda_1} \text{ is the pmf of } Poi(e^t\lambda_1)) \\ \Rightarrow M_X(t) &= e^{e^t\lambda_1}e^{-\lambda_1}=e^{\lambda_1(e^t-1)}, t\in \R. \text{(} e^{\lambda_1(e^t-1)} \text{ is mgf of } Poi(\lambda_1) \text{)}\\ \text{Similarly, }M_Y(t) &=e^{\lambda_2(e^t-1)}. \end{aligned}$
    
    We know that
    
    $\begin{aligned} M_{X+Y}(t) &= M_X(t)M_Y(t) \\ &= e^{\lambda_1(e^t-1)}e^{\lambda_2(e^-1)} \\ &= e^{(\lambda_1+\lambda_2)(e^t-1)} \end{aligned}$
    
    This is the mgf of $Poi(\lambda_1+\lambda_2)$ !
    
    Since the mgf uniquely determines the distribution $X+Y\sim Poi(\lambda_1+\lambda_2)$
    
    In general, if $X_1, X_2, \ldots, X_n$ independent, $X_i\sim Poi(\lambda_i)$ , then $\sum X_i \sim Poi(\sum \lambda_i$

2.7.2. Joint mgf

Definition: Let $X,Y$ be r.v's. Then $M(t_1, t_2):=\mathbb{E}(e^{t_1X+t_2Y})$ is called the joint mgf of $X$ and $Y$ , if the expectation exists for all $t_1\in(-h_1, h_1)$ , $t_2\in(-h_2, h_2)$ for some $h_1, h_2 >0$ .

More generally, we can define $M(t_1,\ldots, t_n)=\mathbb{E}(exp(\sum_{i=1}^n t_iX_i))$ for r.v's $X_1, \cdots,X_n$ , if the expectation exists for $\{(t_1,\cdots, t_n):t_i\in(-h_i,h_i), i=1,\cdots,n\}$ for some $\{h_i>0\}, i=1,\cdots, n$

2.7.2.1. Properties of the joint mgf

$\begin{aligned} M_X(t) &= \mathbb{E}(e^{tX}) \\ &=\mathbb{E}(e^{tX+0Y}) \\ &=M(t,0) \\ M_Y(t) &=M(0, t) \end{aligned}$
$\frac{\partial^{m+n}}{\partial t_1^m \partial t_2^n} M(t_1, t_2)|_{(0,0)} = \mathbb{E}(X^mY^n) \\ \text{the proof is similar to the single r.v. case}$
If $X\perp \!\!\! \perp Y$ $X ⊥ ⊥ Y$ , then $M(t_1, t_2)=M_X(t_1)M_Y(t_2)$ $M (t_{1}, t_{2}) = M_{X} (t_{1}) M_{Y} (t_{2})$
- Proof:
  $\begin{aligned} M(t_1, t_2) &= \mathbb{E}(e^{t_1X+t_2Y}) \\ (X\perp \!\!\! \perp Y) &= \mathbb{E}(e^{t_1X}e^{t_2Y}) \\ &= \mathbb{E}(e^{t_1X})\cdot \mathbb{E}(e^{t_2Y}) \\ &= M_X(t_1)\cdot M_Y(t_2) \end{aligned}$
- Remark: Don't confuse this with the result $X\perp \!\!\! \perp Y\Rightarrow M_{X+Y}(t)=M_X(t)M_Y(t)$ $X ⊥ ⊥ Y \Rightarrow M_{X + Y} (t) = M_{X} (t) M_{Y} (t)$ .
  - $M_{X+Y}(t)\rightarrow$ mgf of $X+Y$ ; single argument function $t$
  - $M(t_1,t_2)\rightarrow$ joint mgf of $(X,Y)$ ; two arguments $t_1, t_2$

3. Conditional distribution and conditional expectation

3.1. Conditional distribution

3.1.1. Discrete case

Definition Let $X$ and $Y$ be discrete r.v's. The conditional distribution of $X$ given $Y$ is given by:

$P(X=x | Y=y) = \frac{(P(X=x, Y=u))}{P(Y=y)}$

$P(X=x|Y=y): f_{X|Y = y}(x).\quad\quad f_{X|Y}(x|y) \leftarrow \text{conditional probability mass function)}$

Conditional pmf is a legitimate pmf: given any $y$ , $f_{X|Y=y}(x) \geq 0, \forall x$

$\sum_x f_{X|Y=y}(x) = 1$

Note that given $Y=y$ , as $x$ changes, the value of the function $f_{X|Y=y}(x)$ is proportional to the joint probability.

$f_{X|Y=y}(x) \propto P(X=x, Y=y)$

This is useful for solving problems where the denominator $P(Y=y)$ is hard to find.

3.1.1.1. Example

$X_1\sim Poi(\lambda_1), X_2\sim Poi(\lambda_2)$ . $X_1\perp\!\!\!\perp X_2$ , $Y=X_1 + X_2$

Q: $P(X_1=k|Y=n)$ ?

Note $P(X_1=k|Y=n) = f_{X_1|Y=n}(k)$

A: $P(X_1=k|Y=n)$ can only be non-zero for $k=0, \cdots, n$ in this case,

$\begin{aligned} P(X_1=k|Y=n) &= \frac{P(X_1=k, Y=n)}{P(Y=n)} \\ & \propto P(X_1=k, Y=n) \\ & = P(X_1=k, X_2=n-k) \\ & = e^{-\lambda_1}\frac{\lambda_1^k}{k!}\cdot e^{-\lambda_2}\frac{\lambda_2^{n-k}}{(n-k)!} \\ & \propto (\frac{\lambda_1}{\lambda_2})^k / k!(n-k)! \end{aligned}$

we can get $P(X=k|Y=n)$ by normalizing the above expression.

$\begin{aligned} P(X_1=k, Y=n) = \frac{(\frac{\lambda_1}{\lambda_2})^k / k!(n-k)!}{\sum_{k=0}^n(\frac{\lambda_1}{\lambda_2})^k/k!(n-k)!} \end{aligned}$

but then we will need to fine $\sum_{k=0}^n(\frac{\lambda_1}{\lambda_2})^k/k!(n-k)!$

An easier way is to compare $\sum_{k=0}^n(\frac{\lambda_1}{\lambda_2})^k/k!(n-k)!$ with the known results for common distribution. In particular, if $X\sim Bin(n, p)$

$\begin{aligned} P(X=k) &= (\stackrel{n}{k})p^k(1-p)^{n-k} \\ &\propto (\frac{p}{1-p})^k/k! (n-k)! \end{aligned}$

$\Rightarrow P(X_1=k|Y=n)$ follows a binomial distributions with parameters $n$ and $p$ given by $\frac{p}{1-p}=\frac{\lambda_1}{\lambda_2} \Rightarrow p=\frac{\lambda_1}{\lambda_1+\lambda_2}$

Thus, given $Y=X_1+X_2=n$ , the conditional distribution of $X_1$ is binomial with parameter $n$ and $\frac{\lambda_1}{\lambda_1+\lambda_2}$

3.1.2. Continuous case

Definition: Let $X$ and $Y$ be continuous r.v's. The conditional distribution of $X$ given $Y$ is given by

$f_{X|Y}(x|y) = f_{X|Y=y}(x) = \frac{f(x,y)}{f_Y(y)}$

A conditional pdf is a legitimate pdf

$\begin{aligned} f_{X|Y}(x|y) \geq 0\quad \quad\quad& x,y\in \R\\ \int_{-\infty}^\infty f_{X|Y}(x|y) dx = 1,\quad &y\in \R \end{aligned}$

3.1.2.1. Example

Suppose $X\sim Exp(\lambda)$ , $Y|X=x \sim Exp(x) = f_{Y|X}(y|x) = x e^{-xy}, y = e$ $\leftarrow$ conditional distribution of $Y$ given $X=x$

Q: Find the condition pdf $f_{X|Y}(x|y)$

$\begin{aligned} f_{X|Y}(x|y) &= \frac{f(x,y)}{f_Y(y)} \\ & \propto f(x,y) \\ & = f_{Y|X}(y|x)\cdot f_X(x) \\ & = xe^{-xy}\lambda e^{-\lambda x} \\ & \propto xe^{-x(y+\lambda)}, \quad\quad x>0, y>0 \end{aligned}$

Normalization ( make the total probability 1)

$\begin{aligned} f_{X|Y}(x|y) & = \frac{xe^{-x(y+\lambda)}}{\int_0^\infty xe^{-x(y+\lambda)}dx} \\ \int_0^\infty xe^{-x(y+\lambda)}dx &= (\frac{1}{\lambda + y})^2 \leftarrow \text{integration by parts} \end{aligned}$

Thus, $f_{X|Y}(x|y) = (\lambda + y)^2xe^{-x(y+\lambda)}$ , $x>0$ .

This is a gamma distribution with parameters $\gamma$ and $\lambda + y$

3.1.2.1. Example 2

Find the distribution of $Z=XY$ .

Attention: the following method is wrong:

$f_Z(z) = \int_0^\infty f_{Y|X}(\frac{z}{x}|x)\cdot f_X(x)dx$

If we want to directly work with pdf's, we will need to use the change of variable formula for multi-variables. The right formula have turns out to be

$\begin{aligned} f_Z(z) & = \int_0^\infty f_{X,Z}(x,z)dx = \int_0^\infty f_{Z|X}(z|x) f_X(x)dx \\ &= \int_0^{\infty} f(x, \frac{z}{x})\cdot \frac{1}{x}dx \\ &= f_{Y|X}(\frac{z}{x}|x) f_X(x)\cdot\frac{1}{x}dx \end{aligned}$

As an easier way is to use cdf, which gives probability rather than density:

$\begin{aligned} P(Z<z) & = P(XY\leq z) \\ & = \int_0^\infty P(XY\leq z|X=x) f_X(x) dx \quad\quad (\text{law of total probability}) \\ &= \int_0^\infty P(Y\leq\frac{z}{x}|X=x)\cdot f_X(x)dx \\ Y|X=x \sim Exp(x) \\ &= \int_0^\infty(1-e^{-x\cdot\frac{z}{x}})\cdot\lambda e^{-\lambda x} dx \\ &= 1 - e^{-z}\int_0^\infty \lambda e^{-\lambda x}dx \\ &= 1-e^{-z} \Rightarrow Z\sim Exp(1) \end{aligned}$

Notation $X,Y|\{ Z = k \}\stackrel{iid}{\sim}\cdots$ means that given $Z=k$ , $X$ and $Y$ are conditionally independent, and they follow certain distribution.

(the conditional joint cdf/pmf/pdf equals the predict of the conditional cdf's/pmf's/pdf's)

3.2. Conditional expectation

We have seen that conditional pmf/pdf are legitimate pmf/pdf. Correspondingly, a conditional distribution is nothing else but a probability distributions. It is simply a (potentially) different distribution, since it takes more information into consideration.

As a result, we can define everything which are previously defined for unconditional distributions also for conditional distributions.

In particular, it is natural to define the conditional expectation.

Definition. The conditional expectation of $g(X)$ given $Y=y$ is defined as

$\mathbb{E}(g(X)|Y=y) = \begin{cases} \sum_{i_1}^\infty g(x_i) P(X=x_u|Y=y) \quad\quad \text{ if } X|Y=y \text{ is discrete} \\ \int_{-\infty}^\infty g(x)f_{X|Y}(x|y) dx \quad\quad\quad\quad\quad \text{ if } X|X=y \text{ is continuous} \end{cases}$

Fix $y$ , the conditional expectation is nothing but the expectation taken under the conditional distribution.

3.2.1. What is $\mathbb{E}(X|Y)\;?$

Different ways to understand conditional expectation

Fix a value $y$ , $\mathbb{E}(g(X)|Y=y)$ is a number
As $y$ changes $\mathbb{E}(g(x)|Y=y)$ becomes a function of $y$ (that each $y$ gives a value): $h(y) =: \mathbb{E}(g(x)|Y=y)$
since $y$ is actually random, we can define $\mathbb{E}(g(x)|Y)=h(Y)$ . This is a random variable
$\mathbb{E}(g(x)|Y))_{(\omega)} = \mathbb{E}(g(x)|Y=Y(\omega)$
$\omega \in \Omega$ this random variable takes value $\mathbb{E}(g(x)|Y=y)$ When $Y=y$
$\Omega \rightarrow \R \\ h(Y)_{(\omega)} = h(Y(\omega))$

3.2.2. Properties of conditional expectation

Linearity (inherited from expectation)

$\mathbb{E}(aX+b | Y = y) = a\mathbb{E}(X|Y=y) +b$

$\mathbb{E}(X+Z|Y=y) = \mathbb{E}(X|Y=y)+\mathbb{E}(Z|Y=y)$
1. $\mathbb{E}(g(X,Y)|Y=y) = \mathbb{E}(g(X,y)|Y=y) \cancel{=} \mathbb{E}(g(X,y)) \text{ when X and Y are not independent}$
Proof (Discrete):

$\mathbb{E}(g(X,Y)|Y=y) =\sum_{x_i}\sum_{y_j}g(x_i,y_j)\cdot P(X=x_i,Y=y_j|Y=y) \\ \\ P(X=x_i,Y=y_j|Y=y) = \begin{cases} \begin{aligned} &0 & \text{ if } y_j\cancel{=}y \\ \\ &P(X=x_1,Y=y_j)/P(Y+y)=P(X=x_i|Y=y) \quad\quad&\text{ if } y_j=y \end{aligned} \end{cases}\\ \begin{aligned} \\\\ \Rightarrow \mathbb{E}(g(X,Y)|Y=y) &= \sum_{x_i}g(x_i,y)\cdot P(X=x_i|Y=y) \\ &= \mathbb{E}(g(X,y)|Y=y) &g(X,y)\text{ regarded as a function of } x \end{aligned}$

In particular,

$\mathbb{E}(g(X)\cdot h(Y) | Y=y) = h(y) \mathbb{E}(g(X)|Y=y)$

$\mathbb{E}(g(X)\cdot h(Y)|Y) = h(Y)\mathbb{E}(g(X)|Y)$
If $X\perp Y$ , then $\mathbb{E}(g(X)|Y=y) = \mathbb{E}(g(X))$

Fact: If $X\perp Y$ , then conditional distribution of $X$ given $Y=y$ is the same as the unconditional distribution of $X$

Proof(Discrete):

$\begin{aligned} & \text{if } X\perp Y \\ & P(X=x_i|Y=y_j) \\ &\quad= P(X=x_i|Y=y_j) / P(Y=y_j) \\ &\quad= P(X=x_i)P(Y=y_j)/P(Y=y_j) \\ &\quad=P(X=x_i) \end{aligned}$
Law of iterated expectation (or double expectation): Expectation of conditionally expectation is its unconditional expectation

$\mathbb{E}(\mathbb{E}(X|Y)))=\mathbb{E}(X)$

$\mathbb{E}(X|Y)$ is a r.v, a function of $Y$ .
Proof(Discrete):

When $Y=y_j$ , the r.v. $\mathbb{E}(X|Y)=\mathbb{E}(X|Y=y_j) = \sum_{x_i}x_iP(X=x_i|Y=y_j)$ . This happens with probability $P(Y=y_j)$

$\Rightarrow \begin{aligned} \mathbb{E}(\mathbb{E}(X|Y)) &= \sum_{y_j}(\sum_{x_i}x_iP(X=x_i|Y=y_j))P(Y=y_j) \\ &= \sum_{x_i}\sum_{y_j} x_iP(X=x_i|Y=y_j)P(Y=y_j) \\ &= \sum_{x_i}x_i\sum_{y_j}P(X=x_i|Y=y_j)P(Y=y_j) &\text{law of total probability} \\ &= \sum_{x_i}x_i P(X=x_i) = \mathbb{E}(X) \end{aligned}$

Alternatively,

$\begin{aligned} &\sum_{x_i}\sum_{y_j} x_i P(X=x_i|Y=y_j)P(Y=y_j) \\ &\quad=\sum_{x_i}\sum_{y_j} x_i P(X=x_i,Y=y_j) & g(X,Y)=X \text{ at } (x_i, y_j)\\ &\quad= \mathbb{E}(X) \end{aligned}$

Example:

$Y$ : # of claims received by insurance company
$X$ : some random parameter

$Y|X\sim Poi(X), X\sim Exp(\lambda)$

a) $\mathbb{E}(Y)$ ?
b) $P(Y=n)$ ?

a)

$Y|X\sim Poi(X) \Rightarrow \mathbb{E}(Y|X=x) = x \Rightarrow \mathbb{E}(Y|X)=X \\ \therefore \begin{aligned} \\ \mathbb{E}(Y) &= \mathbb{E}(\mathbb{E}(Y|X)) \\ &= \mathbb{E}(X) = \frac{1}{\lambda} \end{aligned}$

b)

$\begin{aligned} P(Y=n) &= \int_0^\infty P(Y=n|X=x)f_X(x)dx \\ &= \int_o^\infty \frac{e^{-x}x^n}{n!}\cdot \lambda e^{-\lambda x} dx \\ &= \frac{\lambda}{n!}\int_0^\infty x^n e^{-(\lambda+1)x}dx \\ &= \frac{\lambda}{(\lambda+1)^{n+1}n!}\int_0^\infty((\lambda+1)x)^n e^{-(\lambda+1)x}d(\lambda+1)x \\ &= \frac{\lambda}{(\lambda+1)^{n+1}n!}\Gamma(n+1) &\Gamma(n+1) = n! \text{ ; formula for gamma function or integration by parts} \\ &= \frac{\lambda}{(\lambda+1)^{n+1}} = (\frac{1}{\lambda+1})^n\cdot\frac{1}{\lambda+1} \\ &\Rightarrow Y+1\sim Geo(\lambda/(\lambda+1)) \end{aligned}$

We verify that $\mathbb{E}(Y)=\frac{\lambda +1}{\lambda}-1=\frac{1}{\lambda}$

3.3. Decomposition of variance (EVVE's low)

Definition: The conditional variance of $Y$ given $X=x$ is defined as

$Var(Y|X=x)=\mathbb{E}((Y-\mathbb{E}(Y|X=x))^2|X=x)$

$Var(Y|X)_{(\omega)} = Var(Y|X=X_{(\omega)}) \quad \quad Var(Y|X)_{(\omega)} \text{: a r.v, a function of }X$

The conditional variance is simply the variance taken under the conditional distribution

$\Rightarrow V(Y|X=x)=\mathbb{E}(Y^2|X=x)-(\mathbb{E}(Y|X=x))^2$

Thus

$Var(Y)=\mathbb{E}(Var(Y|X))+Var(\mathbb{E}(Y|X))$

$\mathbb{E}(Var(Y|X)): \text{"intra-group variance" } \quad\quad Var(\mathbb{E}(Y|X)): \text{"inter-group variance"}$

Proof:

$\begin{aligned} RHS &= E(E(Y^2|X)-(E(Y|X))^2) + E((E(Y|X))^2) - (E(E(Y|X)))^2 \\ &=E(E(Y^2|X)) - \sout{E((E(Y|X))^2)} + \sout{E((E(Y|X))^2)} - (E(E(Y|X)))^2 \\ &=E(Y^2) - (E(Y))^2 \\ &=Var(Y) \end{aligned}$

4. Stochastic Processes

Stochastic Processes

sequence / family of random variables
a random function (hard to formulate)

Definition: A stochastic process $\{X_t\}_{t\in T}$ is a collection of random variables, defined on a common probability space.

$T$ : index set. In most cases, $T$ corresponds to time, and is either discrete $\{0,1,2,\cdots\}$ or continuous $[0,\infty)$

In discrete case, we writes $\{X_n\}_{n=0,1,2,\ldots}$

This state space $S$ os a stochastic process is the set of all possible value of $X_t, t\in T$

$S$ can also be either discrete or continuous. In this course, we typically deal with discrete state space. Then we relabel the states so that $S=\{0,1,2,\cdots\}$ (countable state space) or $S=\{0,1,2,\cdots,M\}$ (finite state space)

Remark: As in the case of the joint distribution, we need the r.v's in a stochastic process to be defined on a common probability space, because we want to discuss their joint behaviours, i.t, how things change over time.

Stochastic Processes Graph

Thus, we can identify each point $\omega$ in the sample space $\Omega$ with a function defined on $T$ and taking value in $S$ . Each function is called a path of this stochastic process

Example Let $X_0, X_1, \cdots$ be independent and identical r.v's following some distribution. Then $\{X_n\}_{n=0,1,2,...}$ is a stochastic process

Stochastic Processes Example1

Example Let $X_1, X_2,...$ be independent and identical r.v.'s. $P(X_1=1)=p$ , and $P(X_1=-1)=1-p$ . Define $S_0=0, S_n=\sum_{i=1}^n X_i, n\leq 1$ , e.g.

$S_0=0$
$S_1=X_1$
$S_2=X_1+X_2$
$\cdots\cdots$

Then $\{S_n\}_{n=0,1,...}$ is a stochastic process, with state space $S=\Z$ (integer)

Stochastic Processes Example2

4.1. Markov Chain

4.1.1. Simple Random Walk

$\{S_n\}_{n=0,1,...}$ is called a "simple random walk". ( $S_n=S_{n-1}+X_n$ )

$S_n=\begin{cases} S_{n-1} + 1 \\ S_{n-1} - 1 \end{cases}$

Remark: Why we need the concept of "stochastic process"? Why don't we just look at the joint distribution of $(X_0, X_1,...,X_n)$ ?

Answer: The joint distribution of a large number of r.v's is very complicated, because it does not take advantage of the special structure of $T$ (time).

For example, simple random walk. The full distribution of $(S_0, S_1, ..., S_n)$ is complicated for $n$ large. However, the structure is actually simple if we focus on the adjacent times:

$S_{n+1}=S_n+X_{n+1}$

$S_n: \text{ last value. } \quad X_{n+1}: \text{related to }Ber(p). \text{ They are independent}$

By introducing time into the framework, we can greatly simplify many things.

More precisely, we find that for simple random walk, $\{S_n\}_{n=0,1,...}$ , if we know $S_n$ the distribution of $S_n+1$ will not depend on the history $(S_0, ..., S_{n-1})$ . This is a very useful property

In general for a stochastic process $\{X_n\}_{n=0,1,...}$ , at time $n$ , we already know $X_0, X_1,..., X_n$ , $S_0$ ; our best estimate of the distribution of $X_{n+1}$ should be the conditional distribution:

$X_{n+1}|X_n,...,X_n$

given by:

$P(X_{n+1}=x_{n+1}|X_n=x_n,..., X_0=x_0)$

As time passes, the expression becomes more and more complicated $\rightarrow$ impossible to handle.

However, if we know that this conditional distribution is actually the same as the conditional distribution only given $X_n$ , then the structure will remain simple for any time. This motivates the notion of Markov chain.

4.1.2. Markov Chain

4.1.2.1. Discrete-time Markov Chain

Definition and Examples

Definition: A discrete-time Stochastic process $\{X_n\}_{n=0,1,...}$ is called a discrete-time Markov Chain (DTMC), if its state space $S$ is discrete, and it has the Markov property:

$\begin{aligned} &\quad P(X_{n+1}=x_{n+1}|X_n=x_n,...,X_o=x_o) \\ &= P(X_{n+1}=x_{n+1}|X_n=x_n) \end{aligned}$

for all $n, x_0,...,x_n,x_{n+1}\in S$

If $X_{n+1}|\{x_n=i\}$ does not change over time, $P(X_{n+1}=j|N_n=i)=P(X_1=j|X_0=i)$ , then we call this Markov chain time-homogeneous (default setting for this course).

$\begin{aligned} &\quad P(X_{n+1}=x_{n+1}|X_n=x_n,...,X_0=x_0 ) \quad\quad &X_{n+1}=x_{n+1}\text{: future; } X_{n}=x_{n}\text{: present(state)} \\ &= P(X_{n+1}=x_{x+1}|X_n=x_n) &X_{n-1}=x_{n-1},...,X_{0}=x_{0}\text{: past(history)} \end{aligned}$

Intuition: Given the present state, the past and the future are independent. In other words, the future depends on the previous results only through the current state.

Example: simple random walk

The simple random walk $\{S_n\}_{n=0,1,...}$ is a Markov chain

Proof:

Recall that $S_{n+1}=S_n+X_{n+1}$

if $s_{n+1}\cancel{=} s_n \pm 1$

$\begin{aligned} &\quad P(S_{n+1}=s_{n+1}|S_n=s_n,...,S_0=s_0) \\ & = 0 \\ & = P(S_{n+1}=s_{n+1}|S_n=s_n) \end{aligned}$

$\begin{aligned} &\quad P(S_{n+1}=s_n+1|S_n=s_n,...,s_0=0) \\ &=P(X_{n+1}|S_n=s_n,...,S_0=0) \\ &=P(X_{n+1}=1) \quad\quad\quad X_{n+1} \perp (X_1,...,X_n) \text{ hence also } (S_0, ..., S_n) \end{aligned}$

Similarly,

$\begin{aligned} &\quad P(S_{n+1}=s_n+1|S_n=s_n) \\ &=P(X_{n+1}=1|S_n=s_n) \\ &=P(X_{n+1}=1) \\ &\Rightarrow P(S_{n+1}|S_n=s_n,...,S_0=s_0) \end{aligned}$

Similarly,

$\begin{aligned} &\quad P(S_{n+1}=s_n-1|S_n=s_n,...,S_0=0) \\ &=P(S_{n+1}=s_n-1|S_n=s_n) \\ &=P(X_{n+1}=-1) \\ &\Rightarrow \{S_n\}_{n=0,1,...} \text{ is a DTMC} \quad\quad\blacksquare \end{aligned}$

4.1.3. One-step transition probability matrix

For a time-homogeneous DTMC, define

$\begin{aligned} P_{ij} &= P(X_1=j|X_0=i) \\ &= P(X_{n+1}=j|X_n=i) \quad\quad n=0,1,... \end{aligned}$

$P_{ij}$ : one step transition probability

The collection of $P_{ij}, i,j\in S$ governs all the one-step transitions of the DTMC. Since it has two indices $i$ and $j$ ; it naturally forms a matrix $P=\{P_{ij}\}_{i,j\in S}$ , called the (one-setp) transition (probability) matrix or transition matrix

Property of a transition matrix $P=\{P_{ij}\}_{i,j\in S}$ :

$\begin{aligned} &P_{ij}\geq 0\quad \forall i,j\in S \\ &\sum_{j\in S}P_{ij}=1 \quad \forall i\in S \quad\rightarrow\text{ the row some of } P \text { are all }1 \end{aligned}$

Reason:

$\begin{aligned} \sum_{j\in S}P_{ij} &=\sum_{j\in S} P(X_1=j|X_0=i) \\ &= P(X_1\in S|X_o=i) \\ &= 1 \end{aligned}$

Example 4.1.3.1. simple random walk

There will be 3 cases:

$\begin{aligned} & P_{i,i+1} = P(S_1=i+1|S_0=i) = P(X_1=1)= p \\ & P_{i,i-1} = P(S_1=i-1|S_0=i) = P(X_1=-1) = 1 - p =:q \\ & P_{i,j}=0 \quad\quad\quad\quad\text{ for } j\cancel{=}i\pm 1 \\ \end{aligned}$

$\Rightarrow \text{(infinite dimension)}p=\begin{Bmatrix} ... & ... & ... & ... & ... & ... & ...\\ ... & 0 & p & 0 & ... & ... & ...\\ ... & q & 0& p & ... & ... & ...\\ ...& ... & q & 0 & p & ... & ... \\ ... & ... & ... & q & 0 & p & ... \\ ... & ... & ... & ... & ... & ... & ... \end{Bmatrix}$

Example 4.1.3.2. Ehrenfest's urn

Two urns $A, B$ , total $M$ balls. Each time, pick one ball randomly(uniformly), and move it to the opposite urn.

$X_n: \# \text{ of balls in } A \text{ after step }n$

$S=\{0,1,...,M\}$

$\begin{aligned} P_{ij} & =P(X_1=j|X_0=j) \quad\quad\text{($i$ balls in $A$, $M-i$ balls in $B$)}\\ & =\begin{cases} \begin{aligned} & i/M \quad\quad\quad\quad\quad\quad&j=i-1\\ & (M-i)/M &j=i+1 \\ & 0 &j\cancel{=}i\pm 1 \end{aligned} \end{cases} \end{aligned}$

$p=\begin{Bmatrix} 0 & 1 \\ 1/M & 0 & (M-1)/M \\ &1/M & 0 & (M-1)/M \\ &&2/M & 0 & (M-2)/M \\ ...&...&...&...&...&...&...\\ &&&&(M-1)/M & 0 & 1/M \\ &&&&&1&0 \end{Bmatrix}$

Example 4.1.3.3: Gambler's ruin

A gambler, each time wins 1 with probability $p$ , losses 1 with probability $1-p=q$ . Initial wealth $S_0=a$ ; wealth at time $n$ : $S_n$ . The gambler leaves if $S_n=0$ (loses all money) or $S_n=M>a$ (wins certain amount of money and gets satisfied)

This is a variant of the simple random walk, where we have absorbing barriers( $P_{ii}=1$ ) at $0$ and $M$

$S=\{0,...,M\}$

$P_{ij}=\begin{cases} \begin{aligned} & p \quad\quad & j=i+1, i=1,...,M-1 \\ & q & j=i-1, i=1,...,M-1 \\ & 1 & i=j=0 \text{ or } i=j=M \\ & 0 & \text{otherwise} \end{aligned} \end{cases}$

$p=\begin{Bmatrix} 1 & 0 &...& \\ q & 0 & p & ... \\ ... & q & 0 & p & ... \\ &... & q & 0 & p & ... \\ ...&...&...&...&...&...&...\\ & & & ... & q & 0 & p \\ & & & & ... & 0 & 1 \end{Bmatrix}$

Example 4.1.3.4: Bonus-Malus system

Insurance company has 4 premium levels: 1, 2, 3, 4

Let $X_n\in\{1,2,3,4\}$ be the premium level for a customer at year $n$

$Y_n \stackrel{iid}{\sim}Poi(\lambda) : \text{ \# of claims at year $n$}$

If $Y_n=0$ $Y_{n} = 0$ (no claims)
- $X_{n+1}=max(X_{n-1},1)$
If $Y_n>0$ $Y_{n} > 0$
- $X_{n+1}=min(X_{n} + Y_n,4)$

Denote $a_k=P(Y_n=k), k=0,1,...$

$p=\begin{Bmatrix} a_0 & a_1 & a_2 & (1-a_0-a_1-a_2) \\ a_0 & 0 & a_1 & (1-a_0-a_1) \\ 0 & a_0 & 0 & (1-a_0) \\ 0 & 0 & a_0 & (1-a_0) \end{Bmatrix}$

4.2. Chapman-Kolmogorov equations

Q: Given the (one-step) transition matrix, $P=\{P_{ij}\}_{i,j\in S}$ , how can we decide the n-step transition probability

$\begin{aligned} P_{ij}^{(n)} &:= P(X_n=j|X_0=i) \\ &=P(X_{n+m}=j|X_m=i), \quad m=0,1,... \end{aligned}$

As a special case, let us start with $P_{ij}^{(2)}$ and their collection $p^{(2)}=\{P_{ij}^{(2)}\}_{i,j\in S}$ (also a square matrix, same dimension as $P$ )

Condition on what happens at time $1$ :

$\begin{aligned} P_{ij}^{(2)} &= P(X_2=j|X_0=i) \\ &= \sum_{j\in S} P(X_2=j|X_0=i, X_1=k) \cdot P(X_1=k | X_0=i) \quad \text{conditional law of total probability} \end{aligned}$

4.2.1. Conditional Law of total probability

$\begin{aligned} &\quad P(X_2=j|X_0=i) \\ &=\sum_{k\in S} P(X_2=j, X_1=k | X_0=i) \\ &=\sum_{k\in S} \frac{P(X_2=j, X_1=k, X_0=i)}{P(X_0=i)} \\ &=\sum_{k\in S} \frac{P(X_2=j, X_1=k, X_0=i)}{P(X_1=k, X_0=i)} \cdot\frac{P(X_1=k, X_0=i)}{P(X_0=i)} \\ &=\sum_{k\in S} P(X_2=j|X_0=i,X_1=k)\cdot P(X_1=k|X_0=i) \end{aligned}$

continue on $P_{ij}^{(2)}$

$\begin{aligned} P_{ij}^{(2)} &= P(X_2=j|X_0=i) \\ &= \sum_{j\in S} P(X_2=j|X_0=i, X_1=k) \cdot P(X_1=k | X_0=i) \quad \text{conditional law of total probability} \\ &=\sum_{k\in S} P(X_2=j|X_1=k)\cdot P(X_1=k|X_0=i) \\ &=\sum_{k\in S} P(X_1=j|X_0=k)\cdot P(X_1=k|X_0=i) \\ &=\sum_{k\in S} P_{ik}\cdot P_{kj} \\ &= (P \cdot P)_{ij} \end{aligned}$

Thus, $P^{(2)} = P\cdot P=P^2$

Using the smae idea, for $n,m=0,1,2,3...$ :

$\begin{aligned} P_{ij}^{(n+m)} &=P(X_{n+m}=j|X_0=i) \\ &= \sum_{k\in S}P(X_{n+m}=j|X_0=i, X_m=k) \cdot P(X_m=k|X_0=i) \\ &= \sum_{k\in S}P(X_{n+m}=j|X_m=k) \cdot P(X_m=k|X_0=i) \quad \text{Markov property} \\ &= \sum_{k\in S}P(X_{n}=j|X_0=k) \cdot P(X_m=k|X_0=i) \\ &=\sum_{k\in S} p_{ik}^{(m)}\cdot P_{kj}^{(n)} \\ &=(P^{(m)}\cdot P^{(n)})_{ij} \\ &\Rightarrow P^{(n+m)} = P^{(m)}\cdot P^{(n)} \quad\quad (*) \end{aligned}$

By definition, $P^{(1)}=P$

$\Rightarrow$ $P^{(2)}=P^{(1)}\cdot P^{(1)}=P^2$
$\Rightarrow$ $P^{(3)}=P^{(2)}\cdot P^{(1)}=P^3$
$\cdots\cdots\cdots$
$\Rightarrow$ $P^{(n)}=P^n$

Note:

$n$ $n$ from $P^{(n)}$ $P^{(n)}$ : n-step transition probability matrix
- $P^{(n)}=\{P_{ij}^{(n)}\}_{i,j\in S} \\ P_{ij}^{(n)}=P(X_n=j|X_0=i)$
$n$ $n$ from $P^n$ $P^{n}$ : n-th power of the (one-step) transition matrix
- $P^n=p\cdot...\cdot P \\ P=\{P_{ij}\}_{i,j\in S} \\ P_{ij}=P(X_1=j|X_0=i)$

$(*)$ is called the Chapman-Kolmogorov equations (c-k equation). Entry-wise:

$P_{ij}^{n+m}=\sum_{k\in S}P_{ik}^{(m)}P_{kj}^{(n)}$

Intuition:

ck-equation

"Condition at time $m$ (on $X_m$ ) and sum p all the possibilities"

4.2.2. Distribution of $X_n$

So far, we have seen transition probability $P_{ij}^{(n)}=P(X_n=j|X_0=i)$ . This is not the probability $P(X_n=j)$ . In order to get this distribution, we need the information about which state the Markov chain starts with.

Let $\alpha_{0,i}=P(X_0=i)$ . The row vector $\alpha_0=(\alpha_{0,0},\alpha_{0,1},...)$ is called the initial distribution of the Markov chain. This is the distribution of the initial state $X_0$

Similarly, we define distribution of $X_n$ : $\alpha_n=(\alpha_{n,0},\alpha_{n,1},...)$ where $\alpha_{n,i}=P(X_n=i)$

Fact: $\alpha_n=\alpha_0\cdot p^n$

Proof:

$\forall j \in S \\\\ \begin{aligned} \alpha_{n,j} &=P(X_n=j) \\ &= \sum_{i\in S} P(X_n=j|X_0=i)\cdot P(X_0=i) \\ &= \sum_{i\in S} \alpha_{0,i}\cdot P_{ij}^{(n)} \\ &=(\alpha_0\cdot P^{(n)})_j = (\alpha_0\cdot P^n)_j \\ \end{aligned}$

$\Rightarrow \alpha_n =\alpha_0\cdot P^n$

$\alpha_n$ : distribution of $X_n$
$\alpha_0$ : initial distribution
$P^n$ : transition matrix

Remark: The distribution of a DTMC is completely determined by two things:

the initial distribution $\alpha_0$ (row vector), and
the transition matrix $P$ (square matrix)

4.3. Stationary distribution (invariant distribution)

Definition: A probability distribution $\pi = (\pi_0,\pi_1,...)$ is called a stationary distribution(invariant distribution) of the DTMC $\{X_n\}_{n=0,1,...}$ with transition matrix $P$ , if :

$\underline{\pi}=\pi\cdot P$
$\sum_{i\in S}\pi_i = 1 (\Leftrightarrow \underline{\pi} \cdot 1\!\!\!\!\perp)$ . ( $1\!\!\!\!\perp$ : a column of all 1's)

Why such $\underline{\pi}$ is called stationary/invariant distribution?

$\sum_{i\in S} \pi_i = 1, \pi_i \geq 0, i=0,1,... \Rightarrow \text{distribution} \\ \underline{\pi} = \pi\cdot P \Rightarrow \text{invariant/stationary.}$

Assume the MC starts from the initial distribution $\alpha_0=\underline{\pi}$ . hen the distribution of $X_1$ is

$\alpha_1 =\alpha_0 \cdot P =\underline{\pi}\cdot P = \underline{\pi} = \alpha_0$

The distribution of $X_2$ :

$\alpha_2=\alpha_0\cdot P^2 =\underline{\pi}\cdot P\cdot P = \underline{\pi} \cdot P = \underline{\pi} = \alpha_0$

$\cdots\cdots$

$\alpha_n=\alpha_0$

Thus, if the MC starts from a stationary distribution, then its distribution will not change over time.

Example 4.3.1

An electron has two states: $ground(0), excited(1)$ . Let $X_n\in\{0,1\}$ be the state at time $n$ .

At each step, changes state with probability:

$\alpha$ if it is in state $0$ .
$\beta$ if it is in state $1$ .

Then $\{X_n\}$ is a DTMC. Its transitional matrix is:

$P=\begin{Bmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{Bmatrix}$

Now let us solve for the stationary distribution $\underline{\pi} =\underline{\pi}\cdot P$ .

$(\pi_0,\pi_1) \begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix} =(\pi_0,\pi_1)$

$\Rightarrow \begin{cases} \pi_0(1-\alpha) + \pi_1\beta=\pi_0\quad(1) \\ \pi_0\alpha + \pi_1(1-\beta) = \pi_1\quad(2) \end{cases}$

We have two equations and two unknowns. However, note that they are not linearly independent:

sum of LHS $=\pi_0+\pi_1=$ sum of RHS. Hence $(2)$ can be derived from $(1)$ . By $(1)$ , we have:

$\alpha\pi_0=\beta\pi_1\quad\text{or}\quad\frac{\pi_0}{\pi_1}=\frac{\beta}{\alpha}$

This where we need $\underline{\pi}\cdot1\!\!\!\!\perp$ :

$\pi_0+\pi_1=1 \Rightarrow\pi_0=\frac{\beta}{\alpha+\beta},\quad \pi_1 =\frac{\alpha}{\alpha+\beta}$

Thus, we conclude that there exists a unique stationary distribution $(\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})=\underline{\pi}$

The above procedure for solving for stationary distribution is typical:

Use $\underline{\pi}=\underline{\pi}P$ to get the properties between different components of $\underline{\pi}$
Use $\underline{\pi}\cdot 1\!\!\!\!\perp = 1$ to normalize (get exact values)

4.4. Classification of States

4.4.1. Transience and Recurrence

Let $T$ : be the waiting for a MC to visit/revisit state $i$ for the first time

$T_i:=min\{n>0:X_n=i\}\quad\quad T_i \text{ is a r.v.}$

$T_i=\infty$ if the MC never (re)visits state $i$ .

Definition 4.4.1. Transience and Recurrence

A state $i$ is called:

transient, if $\mathbb{P}(T_i<\infty|X_0=i) < 1$ (never goes back to $i$ positive probability)
recurrent, if $\mathbb{P}(T_i<\infty|X_0=i) = 1$ $P (T_{i} < \infty ∣ X_{0} = i) = 1$ (always goes back to state $i$ $i$ )
- positive recurrent, if $\mathbb{E}(T_i|X_0=i)<\infty$
- null recurrent, if $\mathbb{E}(T_i|X_0=i)=\infty$
- (note: a r.v. is finite with probability $\cancel{\Rightarrow}$ $\Rightarrow$ its expectation is finite)
  - Example: $T=2,4,...,2^n, p=\frac{1}{2},\frac{1}{4},...,2^{-n}\\$ $\mathbb{E}(T)=2\cdot\frac{1}{2} + 4\cdot\frac{1}{4}+...+2^n\cdot 2^{-n}=\infty$

Example 4.4.1

$P=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} \\ \\ & \frac{1}{2} & \frac{1}{2} \\ \\ & & 1 \end{pmatrix}$

Given $X_0=0$ ,

$P(\underbrace{X_1=0}_{T_0=1}|X_0=0)=P(\underbrace{X_1=1}_{T_0=\infty \text{ since state 1}\atop\text{and 2 do not go to 0}}|X_0=0)=\frac{1}{2} \quad\Rightarrow\quad P(T_0<\infty|X_0=0)=\frac{1}{2}<1$

Thus, state $0$ is transient

Similarly, state $1$ is transient.

Given $X_0=2$ ,

$P(X_1=2|X_0=2)\Rightarrow P(T_2<\infty|X_0=2) = 1$

As $E(T_2|X_0=2)=1$ Thus, state $2$ is a positive recurrence.

In general, the distribution of $T_i$ is very hard to determine $\Rightarrow$ need better criteria for recurrence/transience.

Criteria (1): Define $f_{ii}=P(T_i<\infty|X_0=i)$ , and

$V_i= \text{\# of times that the MC (revisits) state i}=\sum_{n=1}^\infty 1\!\!\!\!\perp_{\{X_n=i\}}$

If state $i$ is transient

$P(V_i=k|X_0=j)=\underbrace{f_{ii}^k}_{\text{goes back to}\atop\text{$i$ for $k$ times}}(\underbrace{1-f_{ii}}_{\text{never visits}\atop\text{$i$ again}})$

$\Rightarrow V_i+1\sim Geo(1-f_{ii})$

In particular, $P(V_i<\infty|X_0=i)=1\Rightarrow$ If state $i$ is transient, it is visited away finitely many times with probability 1. The MC will leave state $i$ forever sooner or later.

On the other hand, if state $i$ is recurrent, then $f_{ii}=1$

$P(V_i=k)=0\quad k=0,1,... \Rightarrow P(V_1=\infty)=1$

If the MC starts at a recurrent state $i$ , it will visit that state infinitely many times. $\\$

Criteria (2): In terms of $E(V_i|X_0=i)$ :

$\begin{aligned} &E(V_i|X_0=i)=\frac{1}{1-f_{ii}} - 1 = \frac{f_{ii}}{1-f_{ii}} < \infty &\text{if } f_{ii} < 1, (i \text{ transient}) \\ &E(V_i|X_0=i)=\infty, &\text{if } f_{ii}=1, (i \text{ recurrent}) \end{aligned}$

Criteria (3): Note that

$\begin{aligned} E(V_i|X_0=i) &= E(\sum_{n=1}^\infty 1\!\!\!\!\perp_{\{X_n=i\}}|X_0=i) \\ &= \sum_{n=1}^\infty E( 1\!\!\!\!\perp_{\{X_n=i\}}|X_0=i) \\ &= \sum_{n=1}^\infty P(X_n=i|X_0=i) \\ &=\sum_{n=1}^\infty P_{ii}^{(n)} \end{aligned}$

$\begin{aligned} \Rightarrow &\sum_{n=1}^\infty P_{ii}^{(n)} < \infty &\text{if } i \text{ transient} \\ \Rightarrow &\sum_{n=1}^\infty P_{ii}^{(n)} = \infty &\text{if } i \text{ recurrent} \\ \end{aligned}$

To conclude,

$define:\quad \begin{aligned} i\quad\quad & recureent & transient \\ &P(T_i<infty |X_0=i) = 1 \quad& P(T_i<\infty|X_0=i)<1 \\ &P(V_i=\infty|X_0=i)=1&P(V_i<\infty|X_0=i)=1 \\ &E(V_i|X_0=i)=\infty &E(V_i|X_0=i)<\infty \\ \text{easiest to use: } &\sum_{n=1}^\infty P_{ii}^{(n)}=\infty &\sum_{n=1}^\infty P_{ii}^{(n)}<\infty \end{aligned}$

4.4.2. Periodicity

Example:

$P= \begin{pmatrix} & 1 & & \\ \frac{1}{2} & & \frac{1}{2} & \\ &\frac{1}{2}&&\frac{1}{2}\\ &&1& \end{pmatrix}$

Note that if we starts from 0, we can only get back to 0 in $2, 4, 6,\cdots$ , i.t., even number of steps $P_{00}^{(2n+1)}=0,\quad \forall n$

Definition 4.4.2. Period

The period of state $i$ is defined as

$d_i=\underbrace{gcd}_{\text{greates}\atop\text{common divisor}}(\{n:\underbrace{P_{ii}^{(n)}>0}_{\text{$i$ can go back} \atop\text{to $i$ in $n$ steps} }\})$

In this example above, $d_0=gcd(\{\text{even numbers}\}) = 2$

If $d_i=1$ , state $i$ is called "aperiodic"

If $\cancel{\exists} n > 0$ such that $P_{ii}^{(n)}>0$ , then $d_i=\infty$

Remark 4.4.2

Note that $P_{ii} > 0 \Rightarrow d_i = 1$ . The converse is not true.

$P_{00}^{(2)} >0, P_{00}^{(3)} > 0 \Rightarrow d_0 =1 \text{ but } P_{00}=0$

In general, $d_i=d \cancel{\Rightarrow} P_{ii}^{(d)}>0$

4.4.3. Equivalent classes and irreducibility

Definition 4.4.3.1. Assessable

Let $\{X_n\}_n=0,1,\cdots$ be a DTMC with state space $S$ . State $j$ is said to be $\text{\underline{assessable}}$ from state $i$ , denoted by $i\rightarrow j$ , if $P_{ij}^{(n)}>0$ for some $n\geq 0$ .

Intuitively, $i$ can go to state $j$ in finite steps.

Definition 4.4.3.2. Communicate

If $i\rightarrow j$ and $j\rightarrow i$ , we say $i$ and $j$ communicate, denoted by $i\leftrightarrow j$ .

Fact 4.4.3.1

"Communication" is an equivalence relation.

$i\leftrightarrow j$ then $P_{ii}^{(0)}= 1 \bold{=} P(X_0=i|X_0=i)$ (Identity)
$i\leftrightarrow j$ then $j\leftrightarrow i$ (symmetry)
$i\leftrightarrow j, j\leftrightarrow k$ , then $i\leftrightarrow k$ (transitivity)

Definition 4.4.3.3. Class

As a result, we can use " $\leftrightarrow$ " to divide the state space into different classes, each containing only the states which communicate with each other.

$\begin{cases} S=\bigcup_kC_k \quad\quad\quad\quad \text{($\{C_n\}$ is a partition of $S$)}\\ C_k\bigcap C_k' = \emptyset, k\cancel{=}k' \end{cases}$

For state $i$ and $j$ in the same class $C_k$ , $i\leftrightarrow j$ .
For $i$ $j$ in different classes, $i\cancel{\leftrightarrow} j$ ( $i\cancel{\rightarrow} j$ or $j\cancel{\rightarrow} i$ )

Definition 4.4.3. Irreducible

A MC is called irreducible, if it has only one class. In other words, $i\leftrightarrow j$ for any $i, j\in S$

-Q: How to find equivalent classes?

-A: "Draw a graph and find the loops"

Example 4.4.3.1. Find the classes

$P=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & & \\ \\ \frac{1}{2}&\frac{1}{2}&&\\ \\ \frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\\ \\ &&&1 \end{pmatrix}$

Draw an arrow from $i$ to $j$ if $P_{ij} > 0$

$P_{01}>0, P{10}>0 \Rightarrow 0\leftrightarrow1$
State 2 does not communicate with any other state, since $P_{i2}=0, i\cancel{=}2$
State 3 does not communicate with any other state, since $P_{i3}=0, i\cancel{=}3$

$\Rightarrow$ 3 classes: $\{0,1\}, \{2\}, \{3\}$

Example 4.4.3.2. Find the classes

$P=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & & \\ \\ \frac{1}{2}&&\frac{1}{2}&\\ \\ \frac{1}{2}&&&\frac{1}{2}\\ \\ &&\frac{1}{2}&\frac{1}{2} \end{pmatrix}$

$P_{01}, P_{12}, P_{20} > 0 \Rightarrow 0,1,2$ are in the same class
$P_{23}, P_{32} > 0 \Rightarrow 2,3$ are in the same class
Transitivity $\Rightarrow$ 0,1,2,3 are all in the same class.

$\Rightarrow$ This MC is irreducible

Fact 4.4.3.2

Preposition Transience/Recurrence are class properties. That is, if $i\leftrightarrow j$ , then $j$ is transient/recurrent if and only if $i$ is transient/recurrent

Proof:

Suppose $i$ is recurrent, then $\sum_{k=1}^\infty P_{ii}^{(k)}=\infty$

Since $i \leftrightarrow j$ , $\exists m,n$ such that $P_{ij}^{(m)}>0, P_{ij}^{(n)}>0$

Note that

$\begin{aligned} \underbrace{P_{jj}^{(m+n+k)}}_{P(X_{m+n+k}=j|X_0=j)} \geq \underbrace{P_{ji}^{(n)}P_{ii}^{(k)}P_{ij}^{(m)}}_{P(X_{m+n+k}=j, X_{n+k}=i, X_n=i|X_0=j)} \Rightarrow \sum_{l=1}^\infty P_{jj}^{(l)} &\geq \sum_{l=m+n+1}^\infty P_{jj}^{(l)} \\ & = \sum_{k=1}^\infty P_{jj}^{(m+n+k)} \\ & \geq \sum_{k=1}^\infty P_{ji}^{(n)}P_{ii}^{(k)}P_{ji}^{(m)} \\ & = \underbrace{P_{jj}^{(n)}}_{0}\underbrace{P_{ij}^{(m)}}_{0}\ \underbrace{\sum_{k=1}^\infty P_{ii}^{(k)}}_\infty = \infty \end{aligned}$

Thus, $j$ is recurrent. Symmetrically, $j$ is recurrent $\Rightarrow$ $i$ is recurrent

Thus,

$i$ recurrent $\Leftrightarrow$ $j$ recurrent
$i$ transient $\Leftrightarrow$ $j$ transient

For irreducible MC, since recurrence and transience are class properties, we also say the Markov Chain is recurrent/transient

Definition 4.4.3.5. Proposition

If an irreducible MC has a finite state space, then it is recurrent

Idea of proof

If the MC is transient, then with probability 1, each state has a last visit time. Finite states $\Rightarrow$ $\exists$ a last visit time for all the states. As a result, the MC has nowhere to go after that time. $\Rightarrow$ Contradiction.

Remark 4.4.3.1

We can actually prove that the MC must be positive recurrent, if the state space is finite and the MC is irreducible.

Theorem 4.4.3.1

Periodicity is a class property: $i\leftrightarrow j\Rightarrow d_i=d_j$ .

For an irreducible MC, its period is defined as the period of any state.

4.5. Limiting Distribution

In this part, we are interested in $lim_{n\rightarrow\infty} P_{ij}^{(n)}$ and $lim_{n\rightarrow\infty}P(X_n=i)$

To make things simple, we focus on the irreducible case.

Theorem 4.5.1. Basic Limit Theorem

Let $\{X_n\}_{n=0,1,\ldots}$ be an irreducible, aperiodic, positive recurrent DTMC. Then a unique stationary distribution:

$\underline{\pi}=(\pi_0,\pi_1,\ldots) \text{ exits}$

Moreover:

$(*)\underbrace{lim_{n\rightarrow\infty} P_{ij}^{(n)}}_{\text{limiting distribution}\atop\text{(does not depend on the initial state i)} } =lim_{n\rightarrow\infty} \underbrace{\frac{\sum_{k=1}^n\mathbb{I}_{\{X_k=j\}}}{n}}_{\text{long-run fraction of time spent in j}} =\underbrace{\frac{1}{\mathbb{E}(T_j|X_0=j)}}_{\text{$T_j=min\{n>0:X_n=j\}$}\atop\text{expected revisit time}} =\pi_j\quad\quad, i,j\in S$

Limiting distribution =

long-run fraction of time
$1 /$ expected revisit time
stationary distribution

Remark 4.5.1

The result $(*)$ is still true if the MC is null recurrent, where all the terms are 0, and $\underline{\pi}$ is no longer a distribution. (in other words, there does not exist a stationary distribution)

Remark 4.5.2

If $\{X_n\}_{n=0,1,\ldots}$ has a period $d>1$ :

$\frac{\lim_{n\rightarrow\infty} P_{jj}^{(nd)}}{d} = \lim_{n\rightarrow\infty}\frac{\sum_{k=1}^n\mathbb{I}\mathbb{I}\mathbb{I}\mathbb{I}_{\{X_k=j\}}}{n} = \quad\frac{1}{\mathbb{E}(T_j|X_0=j)}=\pi_j$

Back to the aperiodic case. SInce the limit $\lim_{n\rightarrow\infty}P_{ij}^{(n)}$ does not depend on $i$ , $\lim_{n\rightarrow\infty}P_{ij}^{(n)}=\pi_j$ is also the limiting(marginal) distribution at state $j$ :

$\lim_{n\rightarrow\infty}\alpha_{n,j} = \lim_{n\rightarrow\infty}P(X_n=j)=\pi_j$

regardless of the initial distribution $\alpha_0$

Detail:

$\begin{aligned} \lim_{n\rightarrow\infty}\alpha_{n,j} & = \lim_{n\rightarrow\infty}(\alpha_0\cdot p^{(n)})_j \\ & = \lim_{n\rightarrow\infty}\sum_{i\in S}\alpha_{0,i}\cdot P_{ij}^{(n)} \\ & = \sum_{i\in S}\lim_{n\rightarrow\infty}\alpha_{0,i}\cdot P_{ij}^{(n)} \\ & = \sum_{i\in S}\alpha_{0,i}\lim_{n\rightarrow\infty}\cdot P_{ij}^{(n)} \\ & = (\sum_{i\in S}\alpha_{0,i})\pi_j \\ & = \pi_j \end{aligned}$

Why are the conditions in the Basic Limit Theorem necessary?

Example 4.5.1

Consider a MC with

$p=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} & & \\ \frac{1}{2} & \frac{1}{2} & & \\ & & \frac{1}{2} & \frac{1}{2} \\ & & \frac{1}{2} & \frac{1}{2} \end{pmatrix}$

Two classes: $\{0,1\}, \{2, 3\}$ $\Rightarrow$ it is not irreducible. All the states are still aperiodic, positive recurrent

This MC can be decomposed into two MC's:

State $0, 1$ , with

$p_1=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} \\\\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} \quad\quad \text{irreducible}$

State $2, 3$ , with

$p_1=\begin{pmatrix} \frac{1}{2} & \frac{1}{2} \\\\ \frac{1}{2} & \frac{1}{2} \end{pmatrix} \quad\quad \text{irreducible}$

And

$p=\begin{pmatrix} P_1 & \\ & P_2 \end{pmatrix}$

Note that both $(\frac{1}{2},\frac{1}{2},0,0)$ and $(0,0,\frac{1}{2},\frac{1}{2})$ are stationary distributions. Consequently, any convex combination of these two distributions, of the form:

$a(\frac{1}{2},\frac{1}{2},0,0) + (1-a)(0,0,\frac{1}{2},\frac{1}{2})\quad, a\in\{0,1\}$

is also a stationary distribution

Thus, irreducibility is related to the uniqueness of the stationary distribution.

Correspondingly, the limiting transition probability will depend on $i$ :

$\lim_{n\rightarrow\infty}P_{00}^{(n)} = (\lim_{n\rightarrow\infty}P_1^n)_{00}=\frac{1}{2}$

but $\lim_{n\rightarrow\infty}P_{20}^{(n)}=0$

Example 4.5.2

Consider a MC with

$P = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}$

Irreducible, positive recurrent, but not aperiodic: $d=2$

Note that $P^2=\begin{pmatrix}1&\\&1\end{pmatrix}=I\Rightarrow P^{2n}=\begin{pmatrix}1&\\&1\end{pmatrix}, P^{2n+1}=P=\begin{pmatrix}&1\\1\end{pmatrix}$

$P_{00}^{(n)}=1$ for $n$ even, $0$ for $n$ odd $\Rightarrow$ $\lim_{n\rightarrow\infty}P_{00}^{(n)}$ does not exist.

Aperiodicity is related to the existence of the limit $\lim_{n\rightarrow\infty}P_{ij}^{(n)}$

Example 4.5.3

$P_{0,j} = p_j, j=0,1,\cdots, p_0>0 \\ P_{i,i-1}=1, i\geq 1$

Given $X_0=0$ , $T_0=n+1$ if and only if $X_1=n$ . his happens with prob $p_n$ .

$\begin{aligned} \Rightarrow\mathbb{E}(T_0|X_0=0) &=\sum_{n=0}^\infty (n+1)p_n \\ &=1 + \sum_{n=0}^\infty np_n \end{aligned}$

We can construct $p_n$ such that $\sum_{n=0}^\infty np_n=\infty$ . (For example, $p_0=\frac{1}{2}, p_2=\frac{1}{4}, p_4=\frac{1}{4},\cdots$ )

In this case, the chain is null recurrent. It is irreducible and aperiodic ( $P_{00}=p_0>0$ )

A stationary distribution does not exist. Reason:

$p= \begin{pmatrix} p_0 & p_1& p_2 & \cdots & p_i & \cdots \\ 1 && 0\\ &1\\ \cdots\\ &&&&1 \end{pmatrix} \\ \underline{\pi}\cdot P=\underline{\pi} \Rightarrow$

$\begin{aligned} &p_0\pi_0 + \pi_1 = \pi_0 \\ &p_1\pi_0 + \pi_2 = \pi_1 \\ &\quad\quad\vdots\\ &p_{i-1}\pi_0 + \pi_i = \pi_{i-1} \\ &p_i\pi_0 + \pi_{i+1} = \pi_I \\ \end{aligned}$

Add the first $i$ equations:

$(p_0+\cdots+p_{i-1})\pi_0 + (\cancel{\pi_1}+\cancel{\pi_2}+\cancel{\cdots}+\pi_i) = \pi_0 + \cancel{\cdots} + \cancel{\pi_{i-1}}\\ (p_0+\cdots+p_{i-1})\pi_0 + \pi_i = \pi_0\\ \Rightarrow \pi_i=(1-(p_o+\cdots+p_{i-1}))\pi_0 = \sum_{k=i}^\infty p_k\pi_0$

Try to normalize:

$\begin{aligned} 1 &= \sum_{i=1}^\infty \pi_i \\ &= \sum_{i=0}^\infty\sum_{k_i}^\infty p_k\pi_0 \\ &= \sum_{k_i}^\infty \sum_{i=0}^\infty p_k\pi_0 \\ &= \sum_{k_i}^\infty p_k \sum_{i=0}^\infty\pi_0 \\ &= (\underbrace{\sum_{k_i}^\infty (k+1)p_k }_{\infty})\pi_0 \end{aligned} \\ \Rightarrow \pi_0=0\quad,\quad pi_i=0 \quad\forall i$

This is not a distribution. Thus, a stationary distribution does not exist.

positive recurrence is related to the existence of the stationary distribution

Example 4.5.4. Electron

$P=\begin{pmatrix} 1-\alpha & \alpha \\ \beta & 1-\beta \end{pmatrix} \quad \alpha,\beta\in(0,1)$

Irreducible, aperiodic, positive recurrence.

In order to find of $P^n$ ; we use the diagonalization technique.

$P=Q\Lambda Q^{-1} \quad\text{where $\Lambda$ is diagonal}\\\\ \Lambda = \begin{pmatrix} 1 & 0 \\ 0 & 1-\alpha-\beta \end{pmatrix} \quad Q=\begin{pmatrix} 1 & \alpha \\ 1 & 1-\beta \end{pmatrix} \quad Q^{-1}=\frac{1}{\alpha+\beta}\begin{pmatrix} \beta & \alpha\\ 1 & -1 \end{pmatrix}$

Then

$\begin{aligned} P^n &= (Q\Lambda \cancel{Q}^{-1})(\cancel{Q}\Lambda \cancel{Q}^{-1})\cdots(\cancel{Q}\Lambda Q^{-1}) \\ &= Q\Lambda^nQ^{-1} \\ &= \begin{pmatrix} 1 & \alpha \\ 1 & -\beta \end{pmatrix} \begin{pmatrix} 1 \\ & (1-\alpha-\beta)^n \end{pmatrix} \frac{1}{\alpha+\beta} \begin{pmatrix} \beta & \alpha \\ 1 & -1 \end{pmatrix} \\ &=\frac{1}{\alpha+\beta} \begin{pmatrix} \beta+\alpha(1-\alpha-\beta)^n & \alpha-\alpha(1-\alpha-\beta)^n \\ \beta-\beta(1-\alpha-\beta)^n & \alpha+\beta(1-\alpha-\beta)^n \end{pmatrix}\\ &\Rightarrow \lim_{n\rightarrow\infty}P^n=\frac{1}{\alpha+\beta}\begin{pmatrix} \beta & \alpha \\ \beta & \alpha \end{pmatrix} =\begin{pmatrix} \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \\ \\ \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \end{pmatrix} \end{aligned}$

Note that $\lim_{n\rightarrow\infty} P^n$ has identical rows. This corresponds to the result that $\lim_{n\rightarrow\infty}P_{ij}^{(n)}$ does not depend on $i$

We saw that the stationary distribution $\underline{\pi}=(\frac{\beta}{\alpha+\beta},\frac{\alpha}{\alpha+\beta})$ . So we verity that $\pi_j=\lim_{n\rightarrow\infty} P_{ij}^{(n)}$

Also, given $X_0=0$ , $\mathbb{P}(T_0=1|X_0=0)=1-\alpha$ .

For $k=2,3,\cdots$

$\begin{aligned} \mathbb{P}(T_0=k|X_0=0) &= \mathbb{P}(X_k=0,X_{k-1}=1,\cdots, X_1=1|X_0=0) \\ &=\alpha(1-\beta)^{k-2}\beta\\ &\Rightarrow \mathbb{E}(T_0|X_0=0) \\ &=1\cdot(1-\alpha)+\sum_{k=2}^\infty \alpha(1-\beta)^{k-2}\beta k \\ &=1-\alpha+\sum_{k=1}^\infty\underbrace{\alpha(1-\beta)^{k-2}\beta(k-1)}_{\mathbb{E}(Geo(\beta))}+\sum_{k=2}^\infty\alpha\underbrace{(1-\beta)^{k-2}\beta}_{\text{pmf of Geo($\beta$)}}\\ &=1-\alpha+\alpha\sum_{k=1}^\infty(1-\beta)^{k-2}\beta(k-1)+\sum_{k=2}^\infty\alpha(1-\beta)^{k-2}\beta\\ &=1\alpha+\alpha\cdot\frac{1}{\beta}+\alpha\cdot 1 \\ &=1-\cancel{\alpha}+\frac{\alpha}{\beta}+\cancel{\alpha}\\ &=\frac{\alpha+\beta}{\beta} \end{aligned}$

Hence we verify that $\mathbb{E}(T_0|X_0=0)=\frac{1}{\pi_0}$

4.6. Generating function and branching processes

Definition 4.6.1

Let $\underline{p}=(p_0,p_1,\cdots)$ be a distribution on $\{0,1,2,\cdots\}$ . Let $\xi$ be a r.v. following distribution $\underline{p}$ . That is $\mathbb{P}(\xi=i)=p_i$ . Then the generating function of $\xi$ , or of $\underline{p}$ , is defined by

$\begin{aligned} \psi(s)&=\mathbb{E}(s^\xi) \\ &=\sum_{k=0}^\infty p_ks^k\quad\quad for 0\leq s\leq 1 \end{aligned}$

Properties of generating function

$\psi(0)=p_0,\quad\psi(1)=\sum_{k=0}^\infty p_k=1$
Generating function determines the distribution

$p_k=\frac{1}{k!}\frac{d^k\psi(s)}{ds^k}|_{s=0}$

Reason:

$\psi(s)=p_0+p_1s^1+\cdots+p_{k-1}s^{k-1}+p_ks^k+p_{k+1}s^{k+1}+\cdots \\$

$\frac{d^k\psi(s)}{ds^k}=k!p_k +(\cdots)s +(\cdots)s^2+\cdots$

$\frac{d^k\psi(s)}{ds^k}|_{s=0}=k!p_k$

In particular, $p_1\geq 0\Rightarrow\psi(s)$ is increasing. $p_2\geq 0\Rightarrow \psi(s)$ is climax
Let $\xi_1,...,\xi_n$ be independent r.b. with generating function $\psi_1,...,\psi_n$ ,

$X=\xi_1+...+\xi_n \Rightarrow \psi_X(s)=\psi_1(s)\psi_2(s)...\psi_n(s)$

Proof:

$\begin{aligned} \psi_X(s) &= \mathbb{s^X} \\ (independent) &= \mathbb{E}(s^{\xi_1}s^{\xi_2}...s^{\xi_n}) \\ &= \mathbb{E}(s^{\xi_1})...\mathbb{E}(s^{\xi_n})\\ &= \psi_1(s)...\psi_n(s) \end{aligned}$
$\frac{d^\psi(s)}{ds^k}\bigg|_{s=1} = \frac{d^k\mathbb{E}(s^\xi)}{ds^k}\bigg|_{s=1} = \mathbb{E}(\frac{d^ks^\xi}{ds^k}\bigg|_{s=1} = \mathbb{E}(\xi(\xi-1)(\xi-2)...(\xi-k+1)s^{\xi-k})\bigg|_{s=1} = \mathbb{E}(\xi(\xi-1)...(\xi-k+1))$

In particular, $\mathbb{E}(\xi) = \psi'(1)$ and $Var(\xi)=\mathbb{E}(\xi^2)-(\mathbb{E}(\xi))^2=\mathbb{E}(\xi^2-\xi)+\mathbb{E}(\xi)-(\mathbb{E}(\xi))^2 = \psi''(1)+\psi(1)-(\psi'(1))^2$

Graph of a g.f.:

4.6.1. Branching Process

Each organism, at the end of its life, produces a random number $Y$ of offsprings.

$\mathbb{P}(Y=k)=P_k, \quad k=0,1,2,..., \quad P_k\geq 0,\quad \sum_{k=0}^\infty P_k=1$

The number of offsprings of different individuals are independent.

Start from one ancestor $X_0=1$ , $X_n:$ # of individuals(population in $n$ -th generation)

Then $X_n+1=Y_1^{(n)}+Y_2^{(n)}+...+Y_{X_n}^{(n)}$ , where $Y_1^{(n)},...,Y_{X_n}^{(n)}$ are independent copies of $Y, Y_i^{(n)}$ is the number of offsprings of the $i$ -th individual in the $n$ -th generation

4.6.1.1. Mean and Variance

Mean: $\mathbb{E}(X_n)$ and Variance: $Var(X_n)$

Assume, $\mathbb{E}(Y)=\mu, Var(Y)=\sigma^2$ .

$\begin{aligned} \mathbb{E}(X_{n+1}) &= \mathbb{E}(Y_1^{(n)}+...+Y_{X_n}^{(n)}) \\ &= \mathbb{E}(\mathbb{E}(Y_1^{(n)}+...+Y_{X_n}^{(n)}|X_n)) \\ &= \mathbb{E}(X_n\mu) \\ \text{Wald's identity(tutorial 3)} \quad &= \mu\mathbb{E}(X_n)\\ \end{aligned}$

$\begin{aligned} \Rightarrow \mathbb{E}(X_n) &=\mu\mathbb{E}(X_{n-1}) \\ &=\mu^2\mathbb{E}(X_{n-2}) \\ &\quad\quad\quad\vdots \\ &=\mu^n\mathbb{E}(X_0) = \mu^n,\quad n=0,1,... \end{aligned}$

$\begin{aligned} Var(X_{n+1}) &= \mathbb{E}(Var(X_{n+1}|X_n)+Var(\mathbb{E})X_{n+1}|X_n) \\ \\ \begin{aligned} \mathbb{E}(Var(X_{n+1}|X_n)) &=\mathbb{E}(Var(Y_1^{(n)+...+Y_{X_N}^{(N)}}|X_N))\\ &=\mathbb{E}(X_n\cdot\sigma^2) \\ &= \sigma^2\mu^n \end{aligned}\quad\quad &\begin{aligned} Var(\mathbb{E}(X_{n+1}|X_n)) &= Var(\mu X_n) \\ &= \mu^2Var(X_u)\ \\ &\begin{aligned} \Rightarrow &Var(X_{n+1}) = \sigma^2\mu^n+\mu^2Var(X_n))\\ &Var(X_1)=\sigma^2 \\ &Var(X_2)=\sigma^2\mu + \mu^2\sigma^2=\sigma^2(\mu^1+\mu^2) \\ &Var(X_3)=\sigma^2\mu^2+\mu^2(\sigma^2(\mu^1+\mu^2)) = \sigma^2(\mu^2 + \mu^3 + \mu^4)\\ &\quad\quad\quad\vdots\\ &\text{In general, (can be proved by induction)}\\ &\begin{aligned} Var(X_n)&=\sigma(\mu^{n-1}+...+\mu^{2n-2})\\ &=\begin{cases} \begin{aligned} &\sigma^2\mu^{n-1}\frac{1-\mu^n}{1-\mu} \quad&\mu\cancel{=}1\\ &\sigma^2n &\mu=1 \end{aligned} \end{cases} \end{aligned} \end{aligned} \end{aligned} \end{aligned}$

4.6.1.2. Extinction Probability

Q: What is the probability that the population size is eventually reduced to 0

Note that for a branching process, $X_n=0\Rightarrow X_k=0$ for all $k\geq n$ . Thus, state $0$ is absorbing. $(P_{00}=1)$ . Let $N$ be the time that extinction happens.

$N=min\{n:X_n=0\}$

Define

$U_n=\mathbb{P}(\underbrace{N\leq n}_{\text{extinction happens}\atop\text{before or at n}})=\mathbb{P}(X_n=0)$

Then $U_n$ is increasing in $n$ , and

$\begin{aligned} u=\lim_{n\rightarrow\infty}U_n &= \mathbb{P}(N<\infty) \\ &= P(\text{the extinction eventually happens}) \\ &= \text{extinction probability} \end{aligned}$

Out goal : find $u$

We have the following relation between $U_n$ and $U_{n-1}$ :

$U_n=\sum_{k=0}^\infty P_k(U_{n-1})^k = \underbrace{\psi}_{\text{gf of Y}}(U_{n-1})$

Each subpopulation has the same distribution as the whole population.

Total population dies out in $n$ steps if and only if each subpopulation dies out int $n-1$ steps

$\begin{aligned} U_n &= \mathbb{P}(N\leq n) \\ &= \sum_k \mathbb{P}(N\leq n|X_1 = k)\underbrace{\mathbb{P}(X_1=k)}_{=P_k} \\ &=\sum_k \mathbb{P}(\underbrace{N_1\leq n-1}_{\text{\# of steps for subpopulation 1 to die out}},\cdots, N_k\leq n-1|X_1=k)\cdot P_k \\ &= \sum_k P_k\cdot U_{n-1}^k \\ &= \mathbb{E}(U_{n-1}^Y) \\ &= \psi(U_{n-1}) \end{aligned}$

Thus, the question is :

$\quad$ With initial value $U_0=0$ (since $X_0=1$ ), relation $U_n=\psi(U_{n-1})$ . What is $\lim_{n\rightarrow\infty}U_N=u$ ?

Recall that we have

$\psi(0)=P_0\geq 0$
$\psi(1) = 1$
$\psi(s)$ is increasing
$\psi(s)$ is convex

Draw $\psi(s)$ and function $f(s)=s$ between 0 and 1, we have two cases:

The extinction probability $u$ will be the smallest intersection of $\psi(s)$ and $f(s)$ . Equivalently, it is the smallest solution of the equation $\psi(s)=s$ between 0 and 1. Draw $\psi(s)$ and function $f(s)=s$ between 0 and 1, we have two cases:

Reason: See the dynamics on a graph

$\Rightarrow$ $\begin{aligned} &\text{Case } 1: &u < 1 \\ &\text{Case } 2: &u=1 & \text{ (extinction happens for sure.)} \end{aligned}$ .

Q: How to tell if we are in case 1 or in case ?

A: check $\psi'(1)=\mathbb{E}(Y)$

$\begin{aligned} & \psi'1(1) > 1 &\rightarrow &\text{ Case }1\\ & \psi'1(1) \leq 1 &\rightarrow &\text{ Case }2 \end{aligned}$

Thus, we conclude:

$\mathbb{E}(Y) > 1$ $E (Y) > 1$ : an average more than 1 offspring
- $\Rightarrow$ extinction with certain probability smaller than 1. $u$ is the smallest/unique solution between 0 and 1 of $\psi(s) = s$
$\mathbb{E}(Y) \leq 1$ $E (Y) \leq 1$ : an average less than or equal to 1 offspring
- $\Rightarrow$ extinction happens for sure (with probability 1)

5. Poisson Processes

5.1. Counting Process

DTMC is a discrete-time process. That is, the index set $T=\{0,1,2,...\}$ and $\{X_n\}_{n=01,2,3,\cdots}$ .

We also want to consider the cases where time can be continuous,

$\text{Continuous-time processes: } T=[0,\infty\}$

$\{X_t\}_{t\geq 0} \text{ or } \{X_{(t)}\}_{t\geq 0}$

The simplest type of continuous-time process is counting process, which counts the number of occurrence of certain event before time $t$ .

Definition 5.1.1. Counting Process $N(t)$

Let $0\leq S_1\leq S_2\leq\cdots$ be the time of occurrence of some events. Then, the process

$\begin{aligned} N(t) &:= \#\{n:S_n\leq t\} \\ &=\sum_{n=1}^\infty 1\!\!\!\perp_{\{S_n\leq t\}} \end{aligned}$

is called the counting process (of the events $\{S_n\}_{n=1,2,...}$ )

Equivalently, $N(t) = n \iff S_n\leq t< S_{n+1}$

Example 5.1.1

Calls arrive at a call center.

$S_n$ : arrival time of the $n$ -th call
$N(t)$ : the number of calls received before time $t$

Other examples: cars passing a speed reader, atoms having radioactive decay, ...

Properties of a counting process

$N(t)\geq 0, t\geq 0$
$N(t)$ takes integer values
$N(t)$ $N (t)$ is increasing.
- $N(t_1)\leq N(t_2)$ if $t_1\leq t_2$
$N(t)$ $N (t)$ is right-continuous
- $N(t) = \lim_{s\downarrow t}N(s)$

We also assume:

$N(0) = 0$ (No event happens at time 0)
$N(t)$ $N (t)$ only has jumps at size 1.
- (No two events happen at exactly the same time)

5.2. Definition of Poisson Process

Interarrival Times

$W_1, W_2, \ldots$
$W_1=S_1$
$W_n=S_n-S_{n-1}$ : interarrival time between $n-1$ -th and the $n$ -th event

Definition 5.2.1. Renewal Process

A renewal process is a counting process for which the interarrival times $W_1, W_2, ...$ are independent and identical

ALl the three processes examples of counting processes can be reasonably modeled as renewal processes.

Definition 5.2.2. Poisson Process

Poisson Process $\{X_{(t)}\}_{t\geq0}$ is a renewal process for which the interarrival times are exponentially distributed:

$W_n \stackrel{i.i.d}{\sim} Exp(\lambda)$

A Poisson process $\{N(t)\}_{t\geq 0}$ can be denoted as

$\{N(t)\}\sim Poi(\underbrace{\lambda}_{intensity} t)$

Recall : Properties of the Exponential Distributions

$X\sim Exp(\lambda)$

Basic properties
- pdf: $f(x)=\lambda e^{-\lambda x}\quad(x>0)$
- cdf: $F(x)=1-e^{-\lambda x}$
- $\mathbb{E}(x)=\frac{1}{\lambda}$
- $Var(X)=\frac{1}{\lambda^2}$
Memoryless property
- $\mathbb{P}(X>s+t|x>s) = \mathbb{P}{x>t}$
Min ofexponentials
- $X_1,...,X_n$ $X_{1}, . . ., X_{n}$ independent, $X_i\sim Exp(\lambda_i)$ $X_{i} \sim E x p (λ_{i})$ , then
  1. $min(X_1, \cdots, X_n)\sim Exp(\lambda_1+\cdots+\lambda_n)\\$ Proof: it suffices to prove the result for $n=2$
    $\text{Let } Z=min(X_1, X_2), \text{ then}$
    
    $\begin{aligned} \mathbb{P}(Z>z) &= \mathbb{P}(X_1>z, X_2>z)\\ &= \mathbb{P}(X_1>z)\cdot \mathbb{P}(X_2>z) \\ &= e^{-\lambda_1z}\cdot x^{-\lambda_2z} \\ &= e^{-(\lambda_1+\lambda_2)z} \end{aligned}$
    
    $\Rightarrow\mathbb{P}(Z\leq z) = \underbrace{1-e^{-(\lambda_1+\lambda_2)z}}_{\text{cdf of $Exp(\lambda_1+\lambda_2)$}}\quad z>0$
    
    $Z\sim Exp(\lambda_1+\lambda_2)$
  2. $\mathbb{P}(X_i=min(X_1,\cdots,X_2))=\frac{\lambda_i}{\lambda_1+\cdots+\lambda_n}\\$ Proof: (again for $n=2$ )
    $\begin{aligned} &\mathbb{P}(X_1=min(X_1,X_2)) \\ &= \mathbb{P}(X_1\leq X_2) \\ &= \mathbb{E}(\mathbb{P}(X_1\leq X_2|X_1)) \\ &= \mathbb{E}(e^{-\lambda_2X_1}) \\ &= \int_0^\infty e^{-\lambda_2x}\lambda_1e^{-\lambda_1x} dx \\ &= \lambda_1\int_0^\infty e^{-(\lambda_1+\lambda_2)x}dx \\ &= \frac{\lambda_1}{\lambda_1+\lambda_2} \end{aligned}$

5.3. Properties of Poisson Processes

5.3.1. Continuous-time Markov Property

$\begin{aligned} &\mathbb{P}(N(t_m)=j|N(t_{m-1})=i,N(t_{m-2})=i_{m-2},\cdots, N(t_1)=i_1) \\ &\mathbb{P}(N(t_m)=j|N(t_{m-1}=i)) \end{aligned}$

for any $m$ , $t_1<\cdots<t_m$ , $i_1,i_2,\cdots, i_{m-2},i,j\in S$

Fact 5.3.1.1

The Poisson Process is the only renewal process having the Markov Property

Reason:

Since the exponential distribution is memoryless, the future arrival times will not depend on how long we have waited $\Rightarrow$ The future of the counting process only depends on its current value.

In fact,

$\begin{aligned} &\mathbb{P}(N(t+s)=j|N(s)+j) \\ \text{time homogeneity}&= \mathbb{P}(N(t)=j|N(0)=i) \quad\text{only difference by which number we start ti ciybt}\\ &= \mathbb{P}(N(t)=j-i|N(0)=0) \end{aligned}$

5.3.1.1. Independent Increments

The Poisson Process has independent increments

$\begin{aligned} t_1<t_2<t_3<t_4 \Rightarrow \underbrace{N(t_2) - N(t_1)}_{\text{increments}} \perp\!\!\!\perp \underbrace{N(t_4)-N(t_3)}_{\text{increments}} \end{aligned}$

Reasons:

Memoryless property of exponential distribution.

5.3.1.2. Poisson Increments

The Poisson Process has Poisson increments

$N(t_2)-N(t_1)\sim Poi(\lambda(t_2-t_1))$

Reason:

Let the arrival times between $t_1$ and $t_2$ be $S_1,cdots, S_N$ , where $N=N(t_2)-N(t_1)$ . Then $W_1=S_1-t$ . $W_2=S_2-S_1$ , $\cdots$ are i.i.d r.v's with distribution $Exp(\lambda)$

$\begin{aligned} N=n\Leftrightarrow &W_1+W_2+\cdots +W_n \leq t_2-t_1\\ &W_1+W_2+\cdots +W_n+W_{n+1} > t_2-t_1 \end{aligned}$

Fact 5.3.1.2

If $W_1,\cdots,W_n$ are i.i.d. r.v's following $Exp(\lambda)$ , then $W_1+\cdots+W_n\sim Erlang(n,\lambda)$ (a special type of $Gamma$ )

$c.d.f: F(x)=1\sum_{k=1}^{n-1}\frac{1}{k!}e^{-\lambda x}(\lambda x)^k$

Thus,

$\begin{aligned} &\mathbb{P}(W_1+W_2+\cdots+W_n\leq t_2-t_1)\\ &=1-\sum_{k=0}^{n-1}\frac{1}{k!}e^{-\lambda(t_2-t_1)}(\lambda(t_2-t_1))^k \end{aligned}$

$\begin{aligned} &\mathbb{P}(W_1+W_2+\cdots+W_n+W_{n+1}\leq t_2-t_1)\\ &=1-\sum_{k=0}^{n}\frac{1}{k!}e^{-\lambda(t_2-t_1)}(\lambda(t_2-t_1))^k \end{aligned}$

$\begin{aligned} \mathbb{P}(N=n) &= \mathbb{P}(W_1+\cdots+W_n\leq t_2+t_1) - \mathbb{P}(W_1+\cdots+W_{n+1}\leq t_2-t_1) \\ &=\frac{1}{n!}e^{-\lambda(t_2-t_1)}(\lambda(t_2-t_1))^n \end{aligned}$

In particular, $N(t)=N(t)-N(0)\sim Poi(\lambda t)$

$\mathbb{E}(N(1))=\lambda \quad \leftarrow \text{intensity: expected number of arrivals in one unit of time}$

5.3.1.3. Combining and Thining of Poisson Process

Theorem:

$\{N_1(t)\}\sim Poi(\lambda_1 t)$

$\{N_2(t)\}\sim Poi(\lambda_2 t)$

$\{N_1(t)\}$ and $\{N_2(t)\}$ are independent

Let $N(t)=N_1(t)+N_2(t)$ , then $\{N(t)\}\sim Poi((\lambda_1+\lambda_2)t)$

The combined Poisson Process is still a Poisson Process, with intensity being the sum of intensities.

Reason: Memoryless property, and

$min(W_1, W_2) \\ W1\sim Exp(\lambda_1)\\ W2\sim Exp(\lambda_2)\\ W_1\perp\!\!\!\perp W_2$

$\Rightarrow$ the combined process is the counting process of events with interarrival time following $Exp(\lambda_1+\lambda_2$

Thinning

Let $\{N(t)\}\sim Poi(\lambda t)$ . Each arrival (customer) is labeled as type 1 or type 2, with probability $p$ and $1-p$ , independently from others.

Let $N_1(t)$ and $N_2(t)$ be the number of customers of type 1and type 2 respectively, who arrived before time $t$ . Then

$\begin{aligned} \{N_1(t)&\sim Poi(p\lambda t)\\ \{N_2(t)&\sim Poi((1-p)\lambda t)\\ \text{and } \{N_1(t)\}& \perp\!\!\!\perp \{N_2(t)\} \end{aligned}$

Reason: This is the inverse procedure of combining two independent Poisson processes into one Poisson process

5.3.1.4 Order Statistics Property

Let $X_1,\ldots,X_n$ be i.i.d. r.v's. The order statistics of $X_1, \ldots, X_n$ are random variables defined as follows.

$\begin{aligned} &X_{(1)} = min\{X_1,\ldots,X_n\} \\ &X_{(2)} = \text{2nd smallest among} X_1,\ldots,X_n \\ &\quad\quad\quad\quad\quad\vdots \\ &X_{(n)} = max\{X_1,\ldots,X_n\} \end{aligned}$

In orher words, $X_{(1)},\ldots,X_{(n)}$ are such that $\{X_{(1)},\ldots,X_{(n)}\}=\{X_1,\ldots,X_n\}$ and $X_{(n)}\leq X_{(2)}\leq\cdots\leq X_{(n)}$

Thus, let $\{N(t(\}\sim Poi(\lambda t)$ . Condition on $N(t)=n$ , the points/arrivals of $N$ in $[0,t]$ are distributed as the order statistics of $n$ i.i.d. uniform r.v's on $[0,t]$

That is

$(S_1,\ldots, S_n | N(t)=n)\stackrel{d}{=} (U_{(1)},\ldots, U_{(n)})$

where, $U_{(1)},\ldots,U_{(n)}$ are the order statistics of $U_1, \ldots, U_n\stackrel{iid}{\sim}Unif[0,t]$

Reason:

$\begin{aligned} f_{S_1|\{N(t)=1\}}(s) &=\frac{f_{S_1}(s)\mathbb{P}(W_2>t-s)}{\mathbb{P}(N(t)=1)} \\ &\propto f_{S_1}(s)\mathbb{P}(\underbrace{W_2}_{Exp(\lambda)}>t-s) \\ &= \lambda e^{-\lambda s} e^{-\lambda(t-s)} \\ &= \underbrace{\lambda e^{-\lambda t}}_{\text{const w.r.t. s}} \end{aligned}$

$\Rightarrow S_1|\{N(t)=1\}\sim Unif[0,t]$

As a result of the order statistics property, we have preposition

$N(s)|\{N(t)=n\}\sim Bin(n,\frac{s}{t})\quad\quad\text{for } s\leq t$

Reason: Given $N(t)=n$ , then

$\begin{aligned} N(s) &= \#\{S_i : S_i\leq s, i=1,2,\ldots,n\} \\ \text{Since $\{U_{(i)}\}$ is a} &= \#\{U_{(i)} : U_{(i)}\leq s, i=1,2,\ldots,n\} \\ \text{ permutation of $\{U_i\}$} &= \#\{U_i : U_i\leq s, i=1,2,\ldots,n\} \\ \end{aligned}$

$U_i\stackrel{iid}{\sim}Unif[0,t]$

$\mathbb{P}(U_i\leq s) = \frac{s}{t}\quad\quad i=1,\ldots,n$

$\Rightarrow N(s)|\{N(t)=n\}\sim Bin(n,\frac{s}{t})$

6. Continuous-Time Markov Chain

6.1. Definitions and Structures

Definition 6.1.1. Continuous-time Stochastic Process

A continuous-time stochastic process $\{X(t)\}_{t\geq 0}$ is called a continuous-time Markov Chain (CTMC), if its state space is at most countable, and it satisfies the continuous-time Markov property:

$\begin{aligned} &\mathbb{P}(X(t_m)=j|X(t_{m-1}=i, X(t_{m-2})=i_{m-2},\ldots, X(t_1)=i_1 \\ =& \mathbb{P}(X(t_m)=j|X(t_{m-1}=i))\\ &\quad\quad \text{for any }m, t_1<t_2<\cdots<t_m, i_1,\ldots, i_{m-2}, i, j\in S \end{aligned}$

As DTMC, typically $S=\{0,\ldots,m\}$ or $\{1,\ldots,m\}$ or $\{0,\pm1,\pm2,ldots\}$

Time is continuous, but the state space is discrete $\Rightarrow$ Process will "jump" between states

It can be regarded as a random step function.

Therefore, we need to specify two things:

When the jumps happen? $\Leftrightarrow$ $\Leftrightarrow$ How long the process stays in a state?
- Given the process is in state $i$ , it will stay in this state for an exponential random time, with parameter denoted as $\lambda_i$
- Reason:
  - Markov property $\Rightarrow$ when the process will jump in the future only depends on its current state, not on how long it has been in the current state $\Rightarrow$ memoryless property $\Rightarrow$ exponential.
- Markov Property $\Rightarrow$ the parameter of the exponential can only depend on the current state $i$ .
When it jumps, where it jumps to.
- The continuous-time Markov Chain will jump according to a transition probability $q_{ij}$ , which only depends on $i$ and $j$
- Reason:
  - Markov property $\Rightarrow$ given $i, \underbrace{q_{ij}}_{future}$ can not depend on anything else.
  - $q_{ij}=\mathbb{P}(X(t) \text{ jumps to } j|X(t) \text{ jumps from } j) \Rightarrow \begin{cases} q_{ij}=0\quad\quad\quad\quad\quad\quad\quad q_{ij}\geq 0, j\cancel{=}i \\ \sum_{j\in S}q_{ij}=\sum_{j\in S, j\cancel{=}i}\quad q_{ij}=1 \end{cases}$
  - Define $Q=\{q_{ij}\}_{i,j\in S}\\Q=\begin{bmatrix} 0&q_{01}&q_{02}&\cdots \\ q_{10}&0&q_{12}&\cdots \\ \vdots&\vdots&\vdots&\vdots \end{bmatrix}$
  - the row sums of $Q$ are 1

A CTMC is fully characterized by $\{\lambda_i\}_{i\in S}$ and $Q=\{q_{ij}\}_{i,j\in S}$

To conclude, a CTMC stays in a state $i$ for an exponential random time $T_i$ ; then jumps to another state $j$ with probability $q_{ij}$ , then stays in $j$ for an exponential random time $T_j$ , $\cdots$ , all the jumps and times spent in different states are independent.

Example 6.1.1.1.

We have seen that the Poisson process satisfy the continuous-time Markov property $\Rightarrow$ it is a CTMC

$\lambda_i=\lambda \quad\quad i\in S=\{0,1,2,\cdots\}$

(interarrival times do not depend on current state. $\Rightarrow$ time spent in different states are i.i.d.)

$q_{i,i+i} = 1\quad\quad q_{ij} = 0 \text{ otherwise}(j\cancel{=}i+1)$

6.2. Generator Matrix

Similar to the discrete-time case, we have the transition probability at time $t$ .

$\begin{aligned} P_{ij}(t) &= \mathbb{P}(X(t)=j|X(0)=i) \\ &= \mathbb{P}(X(t+s)=j|X(s)=i) \quad\quad\text{assume the MC is time-homogeneous} \end{aligned}$

and matrix

$P(t)=\{P_{ij}(t)\}_{i,j\in S}$

$P(t)=\begin{pmatrix} p_{00}(t) & p_{01}(t) & \cdots \\ p_{10}(t) & p_{11}(t) & \cdots \\ \vdots & \vdots & \end{pmatrix}$

The C-K equation still holds

$p(t+s) = P(t)\cdot P(s)$

Proof: $\forall i,j\in S$

$\begin{aligned} P_{ij}(t+s) &= \mathbb{P}(X(t+s)=j|X(0)=i) \\ &= \sum_{k\in S}\mathbb{P}(X(t+s)=j|X(t)=k,\cancel{X(0)=i})\cdot \mathbb{P}(X(t)=k|X(0)=i) \\ &= \sum_{k\in S}\mathbb{P}(X(s)+j|X(o)=k)\cdot\mathbb{P}(X(t)=k|X(0)=i) \\ &= \sum_{k\in S}P_{kj}(s)\cdot P_{ik}(t)\\ &=(P(t)\cdot P(s))_{ij}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\blacksquare \end{aligned}$

Note that we have

$P(0) = I$

$(P_{ii}(0)=\mathbb{P}(X(0)=i|X(0)=i) = 1, P_{ij}(0)=0\text{ for } j\cancel{=}i)$

and

$\lim_{t\rightarrow0^+} P(t)=I$

Actually, we have the following stronger result:

$R:= \lim_{h\rightarrow 0^+}\frac{P(h)-P(0)}{h}=\lim_{h\rightarrow0^+}\frac{P(h)-I}{h}$

exists, and is called the (infinitesimal) generator matrix of $\{X(t)\}_{t\geq 0}$

Entry-wise:

$R_{ij}=\lim_{h\rightarrow0^+}\frac{P_{ij}(h)-P_{ij}(0)}{h} = \begin{cases} \lim_{h\rightarrow0^+}\frac{P_{ii}(h)-1}{h}\leq 0\quad j = i\\ \lim_{h\rightarrow0^+}\frac{P_{ii}(h)}{h}\geq 0\quad\quad j \cancel{=}i \end{cases}$

Relation between $R$ and $\{\lambda_i\}_{i\in S}$ and $Q=\{q_{ij}\}_{i,j\in S}$

$R_{ii}=-\lambda_i\quad,\quad R_{ij}=\lambda_iq_{ij}\quad\quad j\cancel{=}i$

Reason:

$\begin{aligned} R_{ii}=\lim_{h\rightarrow0^+}\frac{P_{ii}(h)-1}{h} = \lim_{h\rightarrow0^+}\frac{\mathbb{P}(T_i>h) - 1}{h} \end{aligned}$

Where $T_i$ is the random time the process stays in $i$ . The equality holds because when $h$ is very small, the probability of having two or more jumps in time $h$ is negligible.

$\mathbb{P}(X(h)=i|X(0)=i) = \mathbb{P}(T_i>h) +o(h)\leftarrow\text{having at least 2 jumps and back to $i$}$

$* a(h)=o(h) \text{ if } \lim_{h\rightarrow 0}\frac{a(h)}{h}=0$

$\begin{aligned} R_{ii} &=\lim_{h\rightarrow 0^+}\frac{\mathbb{P}(\overbrace{T_i}^{Exp(\lambda_i)}>h)}{h}\\ &=\lim_{h\rightarrow 0^+}\frac{e^{-\lambda_i h}-1}{j}\\ &=\lim_{h\rightarrow 0^+}\frac{e^{-\lambda_i h}-e^{-\lambda_i \cdot 0}}{j}\\ &= \frac{de^{-\lambda_i}}{dh}\Big|_{h=0}\\ &= -\lambda_i e^{-\lambda_ih}|_{h=0}=-\lambda_i \\ \end{aligned}\\ \begin{aligned} R_{ij}=\lim_{h\rightarrow 0^+}\frac{P_{ij}(h)}{h} &=\lim_{h\rightarrow0^+}\frac{\mathbb{P}(X(h)=j|X(0)=i)}{h}\\ \text{Only one jump happens two } &=\lim_{h\rightarrow0^+}(\frac{\mathbb{P}(T_i<h,X(T_i)=j)}{h} \\ \text{jumps happen$\rightarrow$ uegligeable} &=q_{ij}\lim_{h\rightarrow0^+}\frac{\mathbb{P}(T_i<h)}{h} \\ &=q_{ij}\lim_{h\rightarrow0^+}\frac{1-e^{-\lambda_ih}}{h} \\ &=q_{ij}\lim_{h\rightarrow0^+}\frac{e^{-\lambda_i0}-e^{-\lambda_ih}}{h} \\ &= q_{ij}(\frac{-de^{-\lambda_ih}}{dh}\Big|_{h=0}) \\ &= q_{ij}\lambda_i \end{aligned} \\$

Thus, we conclude that

$R_{ii}=-\lambda_i,\quad R_{ij}=\lambda_iq_{ij]}$

Note that $R_{ii}\leq 0$ , $R_{ij}\geq 0,$ $j\cancel{=}i$

$\begin{aligned} \sum_{i\in S}R_{ij} &= R_{ii}+\sum_{i\in S, j\cancel{=}i}R_{ij} \\ &= -\lambda_i+\sum_{i\in S, j\cancel{=}i}\lambda_iq_{ij} \quad \leftarrow \sum_{j\in S, j\cancel{=}i}q_{ij}=1 \\ &= -\lambda_i+\lambda_i \\ &= 0 \end{aligned}$

The row sums of $R$ are 0

R=\begin{pmatrix} -\lambda_0 & \lambda_0q_{01} & \lambda_0q_{02} & \cdots \\ -\lambda_1q_{10} & -\lambda_1 & \lambda_1q_{12} & \cdots \\ -\lambda_2q_{20} & \lambda_2q_{21} & -\lambda_2 & \cdots \\ \vdots &\vdots&\vdots&\ddots \end{pmatrix} $$-\lambda_0 $-\lambda_i$ : probability flow / rate going out of state $i$ $\lambda_iq_{ij}$ : probability flow / rate going from $i$ to $j$ From $R$ to $\{\lambda_i\}$ and $Q$: $\quad$ If we know $R$, then $$ \lambda_i=-R_{ii}

$q_{ij} = \frac{-R_{ij}}{R_{ii}}\quad j\cancel{=}i$

Thus, there is a $1-1$ relation between $\{\lambda_i\}_{i\in S} + \{q_{ij}\}_{i,j\in S}$ and $R=\{R_{ij}\}_{i,j\in S}$

$\Rightarrow$ the generator $R$ itself also fully characterizes the transitional behaviour of the CDMC.

Conclusion: $\{\lambda_i\}+\{q_{ij}\}_{i,j\in S}$ and $\{R_{ij}\}_{i,j\in S}$ are two sets of parameters that can be used to specify a CDMC.

Example 6.2.1. Poisson Process

$\lambda_i=\lambda\\ Q=\begin{pmatrix} 0 & 1 \\ & 0 & 1 \\ & & 0 & 1 \\ \\ & & & \ddots &\ddots \\ \end{pmatrix}$

$\begin{aligned} \Rightarrow &R_{ii}=-\lambda_i=-\lambda \quad\quad i=0,1,\ldots\\ &R_{ij}=\lambda_iq_{ij}=\begin{cases} \lambda \quad j=i+1 \\ 0 \quad j\cancel{=}i, i+1 \end{cases} \end{aligned}\\ R=\begin{pmatrix} -\lambda & \lambda \\ &-\lambda & \lambda \\ \\ & & \ddots &\ddots \\ \end{pmatrix}$

Example 6.2.2. 3-tables in a restaurant

Parties of customers arrive according to a Poisson Process with intensity $\lambda$ .

If there are free tables $\rightarrow$ the party is served, and spend an exponential amount of time with average $\frac{1}{\mu}$ (parameter $\mu$ )

If there is no free table $\rightarrow$ the party leaves immediately

Let $X(t)$ be the number of occupied tables at time $t$ $\Rightarrow$ $S=\{0,1,2,3\}$

Since all the interarrival times and service times are exponential and independent, the process $\{X(t)\}$ is a CTMC.

Find $\lambda_i$ and $q_{ij}$ :

For $i=0$ :

$q_{01}=1\quad\quad\quad$ no customer $\rightarrow$ one table occupied
$\lambda_0=\lambda\quad\quad\quad$ $λ_{0} = λ$ leave state 0 $\Leftrightarrow$ $\Leftrightarrow$ one party arrives
- $q_{02}=q_{03}=0$

For $i=1$ :

Potential change of states $\begin{cases}1\rightarrow 2\quad\quad\text{if one party arrives first} \quad\quad\sim Exp(\lambda)\sim T\\1\rightarrow 0\quad\quad\text{if a service is completed first}\sim Exp(\mu)\sim S \end{cases}$
Which one actually happens depends on which time is smaller.

Recall a property of exponential

$min(\underbrace{T}_{Exp(\lambda)}, \underbrace{S}_{Exp(\mu)})\sim Exp(\lambda +\mu) \leftarrow \text{the distribution of the time spent in the current state}$

$\begin{aligned} \mathbb{P}(T<S ) &= \frac{\lambda}{\lambda+\mu} \\ q_{12}=\mathbb{P}(T<S)) &= \frac{\lambda}{\lambda+\mu} \\ q_{10}=1-q_{12}&=\frac{\mu}{\lambda+\mu} \\ q_{13} &= 0 \end{aligned}$

Thus,

$\lambda_1=\lambda+\mu$
$q_{12}=\mathbb{P}(T<S)=\frac{\lambda}{\lambda+\mu}$
$q_{10}=1-q_{12}=\frac{\mu}{\lambda+\mu}$
$q_{13}=0$

Similarly, when 2 tables are occupied.

$T$ : time until next arrival $\sim Exp(\lambda)$
$S_1$ : service time for table 1 $\sim Exp(\mu)$
$S_2$ : service time for table 2 $\sim Exp(\mu)$

$\Rightarrow$ $min(T, S_1, S_2)\sim Exp(\lambda +2 \mu)$

$\mathbb{P}(\underbrace{T<S_1,S_2}_{2\rightarrow 3}) = \frac{\lambda}{\lambda+2\mu}$

Thus,

$\lambda_2 = \lambda + 2\mu$
$q_{23} = \frac{\lambda}{\lambda +\mu}, \quad q_{21}=1-q_{23}=\frac{2\mu}{\lambda+2\mu}$
$q_{20} = 0$

Finally,

$\lambda_3=3\mu$ $\rightarrow$ one service is completed.
$q_{32}=1$
$q_{31}=q_{30}=0$

$Q=\begin{pmatrix} 0 & 1 & 0 & 0 \\ \frac{\mu}{\lambda+\mu} & 0 & \frac{\lambda}{\lambda+\mu} & 0 \\ 0 & \frac{2\mu}{\lambda+2\mu} & 0 & \frac{\lambda}{\lambda+2\mu} \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}\\$

$\lambda_0=\lambda$
$\lambda_1=\lambda + \mu$
$\lambda_2=\lambda + 2\mu$
$\lambda_3=3\mu$

$R_{ii}=-\lambda_1, \quad R_{ij}=\lambda_i q_{ij} \\$

$R=\begin{pmatrix} -\lambda & \lambda & 0 & 0\\ \mu & -(\lambda +\mu) & \lambda & 0 \\ 0 & 2\mu & -(\lambda +2\mu) & \mu \\ 0 & 0 & 3\mu & -3\mu \end{pmatrix}$

We see that $R$ was simpler form than $Q$ . Actually $R_{ij}\quad i\cancel{=}j$ directly corresponds to the "rate" by which the process moves from state $i$ to $j$ . Thus, in practice, we often directly model $R$ rather than getting $\{\lambda_i\}_{i\in S}$ and $Q=\{q_{ij}\}_{i,j\in S}$

6.3. Classification of States

The matrix $Q$ is a transition matrix of a DTMC ( $q_{ij}\geq 0,\quad \sum_{j\in S}q_{ij}=1$ ), It contains all the information about the state changes, but "forget" the time.

Since accessibility, communication, irreducibility, recurrence/transience are only related to the change of states, not the time, these properties will be the same for the CTMC and its discrete skeleton.

For a CTMC $\{X(t)\}_{t\geq 0}$ , we call "state $j$ is accessible from state $i$ ", " $i$ and $j$ communicate", "the process is irreducible", " $i$ is recurrent/transient" if and only if this is the case for its discrete skeleton.

6.3.1. Positive / Null Recurrence

Note that since positive/null recurrence do involve the (expected) amount of time, we can indeed have different results for a CTMC and its discrete skeleton.

Let $R_i$ be the amount of (continuous, random) time the MC (re)visits state $i$ .

A state $i$ is called positive recurrent, if it is recurrent, and $\mathbb{E}(R_i|X(0)=i)<\infty$ . It is called null recurrent, if it is recurrent and $\mathbb{E}(R_i|X(0)=i)=\infty$

As in the discrete-time case, the positive recurrence, null recurrence and transience are class property

6.4. Stationary Distribution

Definition 6.4.1. Stationary Distribution

A distribution $\underline{\pi}=(\pi_0,\pi_1,\cdots)$ is called a stationary distribution of a CTMC $\{X(t)\}_{t\geq 0}$ with generator $R$ is it satisfies:

$\underline{\pi}\cdot R=0 \rightarrow (0,0,\cdots)$
$\sum_{i\in S}\pi_i=1\quad$ ( $\underline{\pi}\cdot 1\!\!\!\!\perp = 1$ )

Q: Why such a $\underline{\pi}$ is called stationary?

A: Assume the process starts from the initial distribution $\underline{\alpha^{(0)}}=\underline{\pi}$ :

$\mathbb{P}(X(0)=i)=\pi_i$

Then the distribution at time $t$ is given by

$\underline{\alpha}^{(t)}=\underline{\alpha}^{(0)}\cdot P(t)=\underline{\pi}\cdot P(t)$

Reason:

$\begin{aligned} \alpha_j^{(t)} &= \mathbb{P}(X(t)=j)\\ &= \sum_{i\in S}\mathbb{P}(X(t)=j|X(0)=i)\mathbb{P}(X(0)=i)\\ &= \sum_{i\in S}P_{ij}(t)\cdot \alpha_i^{(0)}\\ &=(\underline{\alpha}^{(i)}\cdot P(t))_j\\ \end{aligned}$

$\begin{aligned} \Rightarrow \frac{d}{dt}(\underline(\alpha)^{(t)} ) &= \frac{d}{dt}(\underline{\pi}\cdot P(t)) \\ &= \underline{\pi}(\frac{d}{dt} P(t)) \\ \text{c-k equation} &= \underline{\pi}\lim_{n\rightarrow 0^+}\frac{P(t+n)-p(t)}{t} \\ &= \underline{\pi}\lim_{n\rightarrow 0^+}\frac{P(n)P(t)-P(t)}{n} \\ &= \underline{\pi}(\lim_{n\rightarrow 0^+}\frac{P(n) - I}{n})P(t) \\ \underline{0} &= \underline{\pi}\cdot R\cdot P(t) \\ &= \underline(0) \end{aligned}$

$\Rightarrow \underline{\alpha}(t)$ is a constant (vector)

In other words, the distribution of $X(t)$ will not change over time, if the MC start from the stationary distribution.

Fact 6.4.1. Stationary Distribution

If a CTMC starts from a stationary distribution, then its distribution will never change.

Remark 6.4.1. Kolmogorov's Backward Equation

In the above derivation, we also see that

$\frac{d}{dt}(P(t)) = P'(t)=R\cdot P(t)$

This is called the Kolmogorov's Backward Equation

6.4.1. Basic Limit Theorem for CTMC

Let $\{X(t)\}_{t\geq 0}$ be an irreducible, recurrent CTMC. Then

$\lim_{t\rightarrow\infty}P_{ij}(t)=:\pi_j'=\frac{\mathbb{E}(T_j)}{\mathbb{E}(R_j|X(0)=j)} = \frac{1/\lambda_i}{\mathbb{E}(R_j|X(0)=j)}$

In addition, the MC is positive recurrent if and only if an unique stationary distribution exists. In this case, the stationary distribution is $\underline{\pi}'=(\pi_0',\pi_1',\cdots)$

Remark 6.4.1.1

$\frac{\mathbb{E}(T_j)}{\mathbb{E}(R_j|X(0)=j)} = \text{long-run fraction of time spent in state $j$}$

Thus, $\pi_j'$ is also the long-run fraction of time that the process spends in stat $j$ .

6.5. Birth and Death Processes

Definition 6.5.1. Birth and Death Process

A Birth and Death Process is a CTMC such that $S=\{0,1,\cdots, M\}$ , or $S=\{0,1,\cdots\}$ , and $\underline{q_{ij}=0}$ if $\underline{|j-i|>1}$ .

The process can only change to neighbouring states:

$q_{i,i-1}+q_{i,i+1} = 1,\quad i\geq 1$

$q_{01} = 1$

For a birth and death process, we use a new set of parameters:

Denote

$\begin{aligned} &\lambda_i = R_{i,i+1}\quad\quad i=0,1,\cdots\\ &\mu_i = R_{i,i-1}\quad\quad i=1,2,\cdots \end{aligned}\\ R=\begin{pmatrix} -\lambda_0 & \lambda_0 \\ \mu_1&-(\lambda_1+\mu_1)&\lambda_1 \\ & \mu_2&-(\lambda_2+\mu_2)&\lambda_2 \\ &&\mu_3&-(\lambda_3+\mu_3)&\lambda_3 \\\\ &&\quad\quad\quad\ddots&\quad\quad\quad\ddots&\quad\quad\quad\ddots \end{pmatrix}\\ \Rightarrow \begin{aligned} &R_{ii} =-(\lambda_i+\mu_i) \quad i\geq 1 \\ &R_{00} =\lambda_0 \end{aligned}$

$\lambda_i$ 's are called the "birth rates" ( $population + 1$ )

$\mu_i$ 's are called "death rates" ( $population - 1$ )

Example 6.5.1. Previous Example of Restaurant

$R=\begin{pmatrix} -\lambda &\lambda \\ \mu & -(\mu+\lambda) & \lambda\\ & 2\mu & -(2\mu+\lambda) & \lambda\\ &&3\mu & -3\mu\\ \end{pmatrix}$

This is a birth and death process.

Birth rates: $\lambda_i = \lambda \quad\quad\quad i=0,1,2,3$
Death rates: $\mu_i = i\cdot \mu \quad\quad i=1,2,3$

In general, consider a M/M/S queueing system.

M: exponential interarrival time
M: service time is exponential $Exp(\mu)$ (each server)
S: number of servers

$X(t) =$ # of customers in the system at time $t$

Birth rate:
- birth $\Leftrightarrow$ arrival
- $\Rightarrow \lambda_1 = \lambda$
Death rate:
- death $\Leftrightarrow$ service done
- When there are $i$ $i$ customers:
  - Case 1 : $i \leq s$ $i \leq s$
    - $i$ servers are busy. Each $\sim Exp(\mu)$
    - $\Rightarrow$ total death rate $\mu_i=i\cdot \mu$
  - Case 2 : $i > s$ $i > s$
    - $s$ servers are busy, $\mu_i=s\cdot \mu$

Thus, for M/M/S queue,

$\lambda_i=\lambda\\ \mu_i=\begin{cases} i\cdot \mu\quad\quad i\leq s\\ s\cdot \mu\quad\quad i > s \end{cases}$

Example 6.5.2. A Population Model

Each individual gives birth to an offspring with exponential rate $\lambda$ . (i.e. the waiting time until it gets the next offspring $\sim Exp(\lambda)$ ). Each individual dies with exponential rate $\mu$ . Let $X(t)$ be the population size at time $t$ .

The time until the next (potential) birth is the smallest amount the $i$ i.i.d. birth time. $\sim Exp(i\cdot \lambda)$

Thus the birth rate $\lambda_i=i\cdot \lambda\quad i=0,1,2,\cdots$

Similarly, the death rate $\mu_i=i\mu\quad i=1,2,\cdots$

$R=\begin{pmatrix} 0 & 0 \\ \mu & -(\lambda+\mu ) & \lambda \\ & 2\mu & -2(\lambda+\mu) & 2\lambda \\ && \quad\quad\ddots&\quad\quad\ddots& \end{pmatrix}\\ *: \text{0 is absorbing}$

If we do need to know $\{\lambda_i\}$ and $Q$

$\lambda_i = -R_{ii}=i(\lambda+\mu)\quad i\geq 0 \\ q_{i,i+1} = \frac{i\lambda}{i(\lambda+\mu)} = \frac{\lambda}{\lambda+\mu} \quad i\geq1 \quad (*) \\ q_{i,i-1}=\frac{i\mu}{i(\lambda+\mu)}=\frac{\mu}{\lambda+\mu} \quad 1\geq 1\\$

$(*)q_{0,1}=1. \text{ arbitrary since } \lambda_0=0$

$Q=\begin{pmatrix} 0 & 1\\\\ \frac{\mu}{\lambda+\mu} & 0 & \frac{\lambda}{\lambda+\mu}\\\\ &\frac{\mu}{\lambda+\mu} & 0 & \frac{\lambda}{\lambda+\mu}\\\\ && \quad\quad \ddots& \quad\quad \ddots \end{pmatrix}$

We can further add immigration to the system. Individuals are added to the population according to a Poisson process with intensity $\alpha$ .

This will not change the "rate" from $i$ to $i-1$

The time until the next increase in population is now the minimum of two r.v's following $Exp(i\lambda)$ (births) and $Exp(\alpha)$ (immigration).

$\Rightarrow$ rate from $i$ to $i+1$ becomes $i\lambda+\alpha$

$R=\begin{pmatrix} -\alpha & \alpha \\ \mu & -(\lambda+\mu+\alpha) & \lambda + \alpha \\ &2\mu & -(\lambda+2\mu+\alpha) & \lambda + \alpha \\\\ && \quad\quad\ddots& \quad\quad\ddots \end{pmatrix}$

$\begin{aligned} (*) \quad&\lambda_i = R_{i,i+1} = i\lambda +\alpha\quad\quad i=0,1,\cdots\\ &\mu_i = R_{i,i-1} = i\mu \quad\quad\quad\quad i = 1,2,\cdots\\ \end{aligned}\\ (*) \text{ not the "biological" birth rate, but the total rate by which the process goes from $i$ to $i+1$}$

$\{\lambda_i\}$ and $Q$ will change accordingly.

Note that state 0 is no longer absorbing due to the immigration.

As we see, there are two main types of birth and death processes: queueing system and population model. THe key difference between them is that the birth rate in the queueing system is typically a constant (does not depend on the current state $i$ ), while the birth rate in population model increases as $i$ increases.

6.5.1. Stationary Distribution of a Birth and Death Process

$\begin{cases} \underline{\pi}\cdot R = \underline{0}\quad (1)\\ \underline{\pi}\cdot 1\!\!\!\!\perp = \underline1 \quad (2)\\ \end{cases}$

$(\pi_0,\pi_1,\cdots) \cdot \begin{pmatrix} -\lambda_0 & \lambda_0 \\ \mu_1 & -(\lambda_1+\mu_1)&\lambda_1\\ &\mu_2 & -(\lambda_2+\mu_2)&\lambda_2\\\\ && \quad\quad\ddots& \quad\quad\ddots& \quad\quad\ddots \end{pmatrix}$

$(1) \Rightarrow \begin{aligned} &-\lambda_0\pi_0+\mu_1\pi_1 = 0 \Rightarrow\pi_1=\frac{\lambda_0}{\mu_1}\pi_0\\ &\lambda_0\pi_0-(\lambda_1+\mu_1)\mu_1+\mu_2\pi_2 = 0 \end{aligned}$

Add this to the first equation, we have

$-\lambda_1\pi_1+\mu_2\pi_2 = 0 \Rightarrow\pi_2=\frac{\lambda_1}{\mu_2}\pi_1$

In general, adding the first $i$ equations, we have

$-\lambda_0\pi_0+\mu_1\pi_1= 0$

$\lambda_0\pi_0-(\lambda_1+\mu_1)\pi_1+\mu_2\pi_2=0$

$\vdots$

$\lambda_{i-2}\pi_{i-2}-(\lambda_{i-1}+\mu_{i-1}+\mu_i\pi_i)=0$

$-\lambda_{i-1}\pi_{i-1}+\mu_i\pi_i=0$

$\begin{aligned} \Rightarrow \pi_i &= \frac{\lambda_{i-1}}{\mu_i}\pi_{i-1}\\ &=\cdots\\ &=\frac{\lambda_0\lambda_1\cdots\lambda_{i-1}}{\mu_1\mu_2\cdots\mu_i}\pi_0 \end{aligned}$

Use $(2)$ to normalize

$1=\sum_{n=0}^\infty \pi_n = (1+\sum_{n=1}^{\infty}\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}$

$\begin{aligned} \Rightarrow &\pi_0=\frac{1}{1+\sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}}\\ &\pi_i=\frac{\Pi_{j=1}^i\frac{\lambda_{j-1}}{\mu_j}}{1+\sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}} \end{aligned}$

Thus, a stationary distribution exists(the MC is positive recurrent, assuming irreducible) if and only if

$\sum_{n=1}^\infty\Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j } < \infty$

Example 6.5.1.1. M/M/S Queue (cont'd)

$\lambda_i = \lambda\quad\quad\mu_i=\begin{cases} i\mu\quad i\leq s \\ s\mu\quad i>s \end{cases}$

$\begin{aligned} &\sum_{n=1}^\infty \Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j}\\ &= \underbrace{\frac{\lambda}{\mu}+\frac{\lambda}{\mu}\cdot\frac{\lambda}{2\mu}+\cdots+\frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots\frac{\lambda}{s\mu} + \frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots(\frac{\lambda}{s\mu})^2+\frac{\lambda}{\mu}\frac{\lambda}{2\mu}\cdots(\frac{\lambda}{s\mu})^3+\cdots}_{\text{geometric series with ration $\frac{\lambda}{s\mu}$}} \end{aligned}$

$\Rightarrow$ The sum is finite if and only if $\lambda<s\mu$

$\Rightarrow$ the process $\{X(t)\}_{t\geq 0}$ is positive recurrent if and only if $\underbrace{\lambda}_{\text{arrival rate}} < \underbrace{s\mu}_{\text{maximal (total) service rate}}$

Example 6.5.1.2. Population Model (with immigration)

$\lambda_i=i\lambda+\alpha\quad\quad\mu_i=i\mu$

$\sum_{n=1}^\infty \Pi_{j=1}^n\frac{\lambda_{j-1}}{\mu_j} = \sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu}$

$\lim_{j\rightarrow\infty}\frac{(j-1)\lambda+\alpha}{j\mu}=\frac{\lambda}{\mu}$

If $\lambda<\mu$ , then $\quad\sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu}<\infty$ by ratio test.

If $\lambda>\mu$ , then $\quad\sum_{n=1}^\infty\Pi_{j=1}^n\frac{(j-1)\lambda+\alpha}{j\mu}=\infty$ .

If $\lambda=\mu$ , then $\quad\alpha \geq \lambda =\mu$ , the ratio $\frac{(j-1)\lambda+\alpha}{j\mu}\geq 1$ for all $j$

$\Rightarrow$ the terms in the summation is non-decreasing

$\Rightarrow$ the $sum = \infty$

If $\lambda=\mu,\quad \alpha <\lambda = \mu$ ：

Raabe-Duhamel's test: (not required content)

$L:=\lim_{n\rightarrow\infty} n(\frac{a_n}{a_{n+1}}-1)\begin{cases} >1\quad\text{converge}\\ <1\quad\text{diverge}\\ =1\quad\text{inconclusive}\\ \end{cases}$

Here:

$\begin{aligned} L&=\lim_{n\rightarrow\infty}n(\frac{n\mu}{(n-1)\lambda+\alpha})\\ &=\lim_{n\rightarrow\infty}n(\frac{n\lambda-(n-1)\lambda-\alpha}{(n-1)\lambda+\alpha})\\ &=\lim_{n\rightarrow\infty}n(\frac{\lambda-\alpha}{(n-1)\lambda+\alpha})\\ &=\frac{\lambda-\alpha}{\lambda} <1 \end{aligned}$

$\Rightarrow$ the sum $=\infty$

Conclusion

To sum up, the CTMC is positive recurrent if and only if $\lambda<\mu$

Q: What happens if $\lambda_0=0$ ? (0 is absorbing)

The chain is not irreducible; typically two classes:

$\{0\}\quad\quad\quad\quad\quad$ positive recurrent
$\{1,2,\cdots\}\quad \text{ }\text{ }\quad$ transient

But the chain does not necessarily end up with being in state $0$ , because it can also have $X(t)\rightarrow\infty$ . Whether this is a possibility depends on the relation between $\{\lambda_i\}$ and $\{\mu_i\}$ .

STAT 333 Course Note

Table of Contents

1. Fundamental of Probability

1.1. What's Probability

1.1.1. Examples

Example 1

1.2. Probability Models

1.2.1. Examples

1.2.1.1. Example 2

1.2.2. Remark: why do we need the notion of event?

1.3. Conditional Probability

1.4. Independence

1.5. Bayes' rule and law of total probability

1.5.1. Bayes' rule

2. Random variables and distributions

2.1. Random variables

2.2. Discrete random variables and distributions

2.2.1. Examples of discrete distributions

1. Bemoulli distribution

2.Binomial distribution

3.Geometric distribution

4. Poisson distribution

2.3. Continuous random variables and distributions

2.3.1. Example of continuous distribution

2.4. Joint distribution of r.v's

2.5. Expectation

2.5.1. Properties of expectation

2.5.2. Definitions

2.6. Indicator

2.6.1. Example

2.6.1. Example 3

2.7. Moment generating function

2.7.1. Properties of mgf

2.7.2. Joint mgf

2.7.2.1. Properties of the joint mgf

3. Conditional distribution and conditional expectation

3.1. Conditional distribution

3.1.1. Discrete case

3.1.1.1. Example

3.1.2. Continuous case

3.1.2.1. Example

3.1.2.1. Example 2

3.2. Conditional expectation

3.2.1. What is E(X∣Y) ?\mathbb{E}(X|Y)\;?E(X∣Y)?

3.2.2. Properties of conditional expectation

3.3. Decomposition of variance (EVVE's low)

4. Stochastic Processes

4.1. Markov Chain

4.1.1. Simple Random Walk

4.1.2. Markov Chain

4.1.2.1. Discrete-time Markov Chain

Definition and Examples

Example: simple random walk

4.1.3. One-step transition probability matrix

Example 4.1.3.1. simple random walk

Example 4.1.3.2. Ehrenfest's urn

Example 4.1.3.3: Gambler's ruin

Example 4.1.3.4: Bonus-Malus system

4.2. Chapman-Kolmogorov equations

4.2.1. Conditional Law of total probability

4.2.2. Distribution of XnX_nXn​

4.3. Stationary distribution (invariant distribution)

Example 4.3.1

4.4. Classification of States

4.4.1. Transience and Recurrence

Definition 4.4.1. Transience and Recurrence

Example 4.4.1

4.4.2. Periodicity

Definition 4.4.2. Period

Remark 4.4.2

4.4.3. Equivalent classes and irreducibility

Definition 4.4.3.1. Assessable

Definition 4.4.3.2. Communicate

Fact 4.4.3.1

Definition 4.4.3.3. Class

Definition 4.4.3. Irreducible

Example 4.4.3.1. Find the classes

Example 4.4.3.2. Find the classes

Fact 4.4.3.2

Definition 4.4.3.5. Proposition

3.2.1. What is $\mathbb{E}(X|Y)\;?$

4.2.2. Distribution of $X_n$

Definition 5.1.1. Counting Process $N(t)$